Best Time to Buy and Sell Stock using Greedy Approach
In order to maximize the profit, we have to minimize the cost price and maximize the selling price. So at every step, we will keep track of the minimum buy price of stock encountered so far. If the current price of stock is lower than the previous buy price, then we will update the buy price, else if the current price of stock is greater than the previous buy price then we can sell at this price to get some profit. After iterating over the entire array, return the maximum profit.
Follow the steps below to implement the above idea:
- Declare a buy variable to store the min stock price encountered so far and max_profit to store the maximum profit.
- Initialize the buy variable to the first element of the prices array.
- Iterate over the prices array and check if the current price is less than buy price or not.
- If the current price is smaller than buy price, then buy on this ith day.
- If the current price is greater than buy price, then make profit from it and maximize the max_profit.
- Finally, return the max_profit.
Below is the implementation of the above approach:
// C++ code for the above approach
#include <iostream>
using namespace std;
int maxProfit(int prices[], int n)
{
int buy = prices[0], max_profit = 0;
for (int i = 1; i < n; i++) {
// Checking for lower buy value
if (buy > prices[i])
buy = prices[i];
// Checking for higher profit
else if (prices[i] - buy > max_profit)
max_profit = prices[i] - buy;
}
return max_profit;
}
// Driver Code
int main()
{
int prices[] = { 7, 1, 5, 6, 4 };
int n = sizeof(prices) / sizeof(prices[0]);
int max_profit = maxProfit(prices, n);
cout << max_profit << endl;
return 0;
}
// Java code for the above approach
class GFG {
static int maxProfit(int prices[], int n)
{
int buy = prices[0], max_profit = 0;
for (int i = 1; i < n; i++) {
// Checking for lower buy value
if (buy > prices[i])
buy = prices[i];
// Checking for higher profit
else if (prices[i] - buy > max_profit)
max_profit = prices[i] - buy;
}
return max_profit;
}
// Driver Code
public static void main(String args[])
{
int prices[] = { 7, 1, 5, 6, 4 };
int n = prices.length;
int max_profit = maxProfit(prices, n);
System.out.println(max_profit);
}
}
// This code is contributed by Lovely Jain
# Python program for the above approach:
def maxProfit(prices, n):
buy = prices[0]
max_profit = 0
for i in range(1, n):
# Checking for lower buy value
if (buy > prices[i]):
buy = prices[i]
# Checking for higher profit
elif (prices[i] - buy > max_profit):
max_profit = prices[i] - buy
return max_profit
# Driver code
if __name__ == '__main__':
prices = [7, 1, 5, 6, 4]
n = len(prices)
max_profit = maxProfit(prices, n)
print(max_profit)
// C# code for the above approach
using System;
public class GFG {
static int maxProfit(int[] prices, int n)
{
int buy = prices[0], max_profit = 0;
for (int i = 1; i < n; i++) {
// Checking for lower buy value
if (buy > prices[i])
buy = prices[i];
// Checking for higher profit
else if (prices[i] - buy > max_profit)
max_profit = prices[i] - buy;
}
return max_profit;
}
static public void Main()
{
// Code
int[] prices = { 7, 1, 5, 6, 4 };
int n = prices.Length;
int max_profit = maxProfit(prices, n);
Console.WriteLine(max_profit);
}
}
// This code is contributed by lokeshmvs21.
function maxProfit( prices, n)
{
let buy = prices[0], max_profit = 0;
for (let i = 1; i < n; i++) {
// Checking for lower buy value
if (buy > prices[i])
buy = prices[i];
// Checking for higher profit
else if (prices[i] - buy > max_profit)
max_profit = prices[i] - buy;
}
return max_profit;
}
// Driver Code
let prices= [ 7, 1, 5, 6, 4 ];
let n =5;
let max_profit = maxProfit(prices, n);
console.log(max_profit);
// This code is contributed by garg28harsh.
Output
5
Time Complexity: O(N). Where N is the size of prices array.
Auxiliary Space: O(1)
Best Time to Buy and Sell Stock (at most one transaction allowed)
Given an array prices[] of length N, representing the prices of the stocks on different days, the task is to find the maximum profit possible by buying and selling the stocks on different days when at most one transaction is allowed.
Note: Stock must be bought before being sold.
Examples:
Input: prices[] = {7, 1, 5, 3, 6, 4}
Output: 5
Explanation:
The lowest price of the stock is on the 2nd day, i.e. price = 1. Starting from the 2nd day, the highest price of the stock is witnessed on the 5th day, i.e. price = 6.
Therefore, maximum possible profit = 6 – 1 = 5.Input: prices[] = {7, 6, 4, 3, 1}
Output: 0
Explanation: Since the array is in decreasing order, no possible way exists to solve the problem.