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.
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++
// 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 Codeint 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
// Java code for the above approachclass 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 |
Python3
# 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 codeif __name__ == '__main__': prices = [7, 1, 5, 6, 4] n = len(prices) max_profit = maxProfit(prices, n) print(max_profit) |
C#
// C# code for the above approachusing 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. |
Javascript
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 using Recursion and Memoization:
We can define a recursive function maxProfit(idx, canSell) which will return us the maximum profit if the user can buy or sell starting from idx.
- If idx == N, then return 0 as we have reached the end of the array
- If canSell == false, then we can only buy at this index. So, we can explore both the choices and return the maximum:
- buy at the current price, so the profit will be: -prices[idx] + maxProfit(idx+1, true)
- move forward without buying, so the profit will be: maxProfit(idx+1, false)
- If canSell == true, then we can only sell at this index. So, we can explore both the choices and return the maximum:
- sell at the current price, so the profit will be: prices[idx]
- move forward without selling, so the profit will be: maxProfit(idx+1, true)
Below is the implementation of the approach:
C++
#include <bits/stdc++.h>using namespace std;// function to calculate the max profitint maxProfit(int idx, vector<int>& prices, bool canSell){ // We have reached the end of array if (idx == prices.size()) return 0; if (canSell) { // We can only sell the stock return max(prices[idx], maxProfit(idx + 1, prices, canSell)); } else { // We can only buy the stock return max(-prices[idx] + maxProfit(idx + 1, prices, true), maxProfit(idx + 1, prices, canSell)); }}int main(){ vector<int> prices{ 7, 1, 5, 3, 6, 4 }; cout << maxProfit(0, prices, false) << "\n"; return 0;} |
Output
5
Time Complexity: O(N), where N is the size of input array prices[]
Auxiliary Space: O(N)
Best Time to Buy and Sell Stock using Dynamic Programming:
We can optimize the recursive approach by storing the states in a 2D dp array of size NX2. Here, dp[idx][0] will store the answer of maxProfit(idx, false) and dp[idx][1] will store the answer of maxProfit(idx, true).
Below is the implementation of the approach:
C++
// C++ code for the approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum// profit with atmost 1 transactionint maxProfit(vector<int>& prices){ int n = prices.size(); // 2D DP array to store max profit with 0 and 1 stocks vector<vector<int> > dp(n, vector<int>(2)); dp[0][0] = -prices[0]; dp[0][1] = 0; // Loop through prices to calculate max profit at each // day for (int i = 1; i < n; i++) { // choice 1: Buy the stock at i, in which case the // profit we get is the maximum profit we could have // made till i-1 minus the price at i. dp[i][0] = max(dp[i - 1][0], -prices[i]); // choice 2:Sell the stock at i, in which case the // profit we get is the maximum profit we could have // made till i-1 by buying the stock earlier plus // the price at i. dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]); } // Return the maximum profit calculated from the last // day return max(dp.back()[0], dp.back()[1]);}// Driver's codeint main(){ // Given prices vector<int> prices = { 7, 1, 5, 3, 6, 4 }; // Function Call int ans = maxProfit(prices); // Print answer cout << ans << endl; return 0;} |
Java
// Java code for the approachimport java.util.*;public class GFG { public static int maxProfit(List<Integer> prices) { int n = prices.size(); // 2D DP array to store max profit with 0 and 1 // stocks int[][] dp = new int[n][2]; dp[0][0] = -prices.get(0); dp[0][1] = 0; // Loop through prices to calculate max profit at // each day for (int i = 1; i < n; i++) { // choice 1: Buy the stock at i, in which case // the profit we get is the maximum profit we // could have made till i-1 minus the price at // i. dp[i][0] = Math.max(dp[i - 1][0], -prices.get(i)); // choice 2: Sell the stock at i, in which case // the profit we get is the maximum profit we // could have made till i-1 by buying the stock // earlier plus the price at i. dp[i][1] = Math.max( dp[i - 1][1], dp[i - 1][0] + prices.get(i)); } // Return the maximum profit calculated from the // last day return Math.max(dp[n - 1][0], dp[n - 1][1]); } public static void main(String[] args) { // Given prices List<Integer> prices = Arrays.asList(7, 1, 5, 3, 6, 4); // Function Call int ans = maxProfit(prices); // Print answer System.out.println(ans); }}// This code is contributed by Susobhan Akhuli |
Python3
# Python code for the approachdef maxProfit(prices): n = len(prices) # 2D DP array to store max profit with 0 and 1 stocks dp = [[0 for _ in range(2)] for _ in range(n)] dp[0][0] = -prices[0] dp[0][1] = 0 # Loop through prices to calculate max profit at each day for i in range(1, n): # choice 1: Buy the stock at i, in which case the # profit we get is the maximum profit we could have # made till i-1 minus the price at i. dp[i][0] = max(dp[i - 1][0], -prices[i]) # choice 2: Sell the stock at i, in which case the # profit we get is the maximum profit we could have # made till i-1 by buying the stock earlier plus # the price at i. dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]) # Return the maximum profit calculated from the last day return max(dp[-1][0], dp[-1][1])# Driver's codeif __name__ == "__main__": # Given prices prices = [7, 1, 5, 3, 6, 4] # Function Call ans = maxProfit(prices) # Print answer print(ans)# This code is contributed by Susobhan Akhuli |
Javascript
function maxProfit(prices) { const n = prices.length; // 2D DP array to store max profit with 0 and 1 stocks const dp = new Array(n).fill(null).map(() => [0, 0]); dp[0][0] = -prices[0]; dp[0][1] = 0; // Loop through prices to calculate max profit at each day for (let i = 1; i < n; i++) { // choice 1: Buy the stock at i, in which case the profit we get is // the maximum profit we could have made till i-1 minus the price at i. dp[i][0] = Math.max(dp[i - 1][0], -prices[i]); // choice 2: Sell the stock at i, in which case the profit we get is // the maximum profit we could have made till i-1 by buying the stock // earlier plus the price at i. dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]); } // Return the maximum profit calculated from the last day return Math.max(dp[n - 1][0], dp[n - 1][1]);}// Given pricesconst prices = [7, 1, 5, 3, 6, 4];// Function Callconst ans = maxProfit(prices);// Print answerconsole.log(ans); |
Output
5
Time complexity: O(N), where N is the length of the given array.
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
