The price of a stock on each day is given in an array arr[] for N days, the task is to find the maximum profit that can be made by buying and selling the stocks in those days with conditions that the stock must be sold before buying again and stock cannot be bought on the next day of selling a stock. (i.e, rest for at least one day).
Examples:
Input: arr[] = {2, 4, 5, 0, 2}
Output: 4
Explanation: Buy at cost 2 and sell at cost 4, profit = 2. Buy at cost 0 and sell at cost 2, profit = 2. Total profit = 4.Input: arr[] = {2, 0, 5, 1, 8}
Output: 8
Approach :
Consider three states: REST, HOLD, and SOLD.
REST means not doing anything.
HOLD means holding stock (bought a stock and have not sold).
SOLD means state after selling the stock.
To reach the REST state, do nothing.
To reach the HOLD state, buy the stock.
To reach the SOLD state, sell the stock for which first there is a need to buy.
By the above actions, a transition diagram is made.
By using this transition diagram the profit can be found out.
On ith day:
- rest[i] denotes maximum profit made by resting on day i. Since ith day is rest day, the stock might have been sold on (i-1)th day or might not have been sold. The value of rest[i] = max( rest[i-1], sold[i-1]).
- hold[i] denotes maximum profit made by buying on ith day or by buying on some day before ith and resting on ith day. So, the value of hold[i] = max( hold[i-1], rest[i-1]+price[i]).
- sold[i] denotes maximum profit by selling ith day. Stock must have been bought on some day before selling it on the ith day. Hence sold[i] = hold[i-1] + price[i].
Hence, the final answer will be the
maximum of sold[n-1] and rest[n-1].
Below is the implementation of the above approach:
C++
// C++ program for the above problem#include <bits/stdc++.h>using namespace std;int maxProfit(int prices[], int n){ // If there is only one day // for buying and selling // no profit can be made if (n <= 1) return 0; // Array to store Maxprofit by // resting on given day int rest[n] = { 0 }; // Array to store Maxprofit by // buying or resting on the // given day int hold[n] = { 0 }; // Array to store Maxprofit by // selling on given day int sold[n] = { 0 }; // Initially there will 0 profit rest[0] = 0; // Buying on 1st day results // in negative profit hold[0] = -prices[0]; // zero profit since selling // before buying isn't possible sold[0] = 0; for (int i = 1; i < n; i++) { // max of profit on (i-1)th // day by resting and profit // on (i-1)th day by selling. rest[i] = max(rest[i - 1], sold[i - 1]); // max of profit by resting // on ith day and // buying on ith day. hold[i] = max(hold[i - 1], rest[i - 1] - prices[i]); // max of profit by selling // on ith day sold[i] = hold[i - 1] + prices[i]; } // maxprofit return max(rest[n - 1], sold[n - 1]);}// Driver Codeint main(){ int price[] = { 2, 4, 5, 0, 2 }; int n = sizeof(price) / sizeof(price[0]); cout << maxProfit(price, n) << endl; return 0;} |
Java
// Java program for the above problemimport java.io.*;public class GFG{static int maxProfit(int prices[], int n){ // If there is only one day // for buying and selling // no profit can be made if (n <= 1) return 0; // Array to store Maxprofit by // resting on given day int rest[] = new int[n]; // Array to store Maxprofit by // buying or resting on the // given day int hold[] = new int[9]; // Array to store Maxprofit by // selling on given day int sold[] = new int[9]; // Initially there will 0 profit rest[0] = 0; // Buying on 1st day results // in negative profit hold[0] = -prices[0]; // Zero profit since selling // before buying isn't possible sold[0] = 0; for(int i = 1; i < n; i++) { // max of profit on (i-1)th // day by resting and profit // on (i-1)th day by selling. rest[i] = Math.max(rest[i - 1], sold[i - 1]); // max of profit by resting // on ith day and // buying on ith day. hold[i] = Math.max(hold[i - 1], rest[i - 1] - prices[i]); // max of profit by selling // on ith day sold[i] = hold[i - 1] + prices[i]; } // maxprofit return Math.max(rest[n - 1], sold[n - 1]);}// Driver Codepublic static void main(String[] args){ int price[] = { 2, 4, 5, 0, 2 }; int n = price.length; System.out.print(maxProfit(price, n) + "\n");}}// This code is contributed by amal kumar choubey |
Python3
# Python3 program for the above problem def maxProfit(prices, n): # If there is only one day # for buying and selling # no profit can be made if (n <= 1): return 0 # Array to store Maxprofit by # resting on given day rest = [0] * n # Array to store Maxprofit by # buying or resting on the # given day hold = [0] * n # Array to store Maxprofit by # selling on given day sold = [0] * n # Initially there will 0 profit rest[0] = 0 # Buying on 1st day results # in negative profit hold[0] = -prices[0] # zero profit since selling # before buying isn't possible sold[0] = 0 for i in range(1, n): # max of profit on (i-1)th # day by resting and profit # on (i-1)th day by selling. rest[i] = max(rest[i - 1], sold[i - 1]) # max of profit by resting # on ith day and # buying on ith day. hold[i] = max(hold[i - 1], rest[i - 1] - prices[i]) # max of profit by selling # on ith day sold[i] = hold[i - 1] + prices[i] # maxprofit return max(rest[n - 1], sold[n - 1])# Driver Code price = [ 2, 4, 5, 0, 2 ]n = len(price)print(maxProfit(price, n))# This code is contributed by avanitrachhadiya2155 |
C#
// C# program for the above problem using System;class GFG{ static int maxProfit(int[] prices, int n) { // If there is only one day // for buying and selling // no profit can be made if (n <= 1) return 0; // Array to store Maxprofit by // resting on given day int[] rest = new int[n]; // Array to store Maxprofit by // buying or resting on the // given day int[] hold = new int[9]; // Array to store Maxprofit by // selling on given day int[] sold = new int[9]; // Initially there will 0 profit rest[0] = 0; // Buying on 1st day results // in negative profit hold[0] = -prices[0]; // Zero profit since selling // before buying isn't possible sold[0] = 0; for(int i = 1; i < n; i++) { // max of profit on (i-1)th // day by resting and profit // on (i-1)th day by selling. rest[i] = Math.Max(rest[i - 1], sold[i - 1]); // max of profit by resting // on ith day and // buying on ith day. hold[i] = Math.Max(hold[i - 1], rest[i - 1] - prices[i]); // max of profit by selling // on ith day sold[i] = hold[i - 1] + prices[i]; } // maxprofit return Math.Max(rest[n - 1], sold[n - 1]); } // Driver codestatic void Main() { int[] price = { 2, 4, 5, 0, 2 }; int n = price.Length; Console.WriteLine(maxProfit(price, n));}}// This code is contributed by divyeshrabadiya07 |
Javascript
<script>// JavaScript program for the above problemfunction maxProfit( prices, n){ // If there is only one day // for buying and selling // no profit can be made if (n <= 1) return 0; // Array to store Maxprofit by // resting on given day let rest = []; for(let k = 0;k<n;k++) rest.push(0); // Array to store Maxprofit by // buying or resting on the // given day let hold = []; for(let k = 0;k<n;k++) hold.push(0); // Array to store Maxprofit by // selling on given day let sold = []; for(let k = 0;k<n;k++) sold.push(0); // Initially there will 0 profit rest[0] = 0; // Buying on 1st day results // in negative profit hold[0] = -prices[0]; // zero profit since selling // before buying isn't possible sold[0] = 0; for (let i = 1; i < n; i++) { // max of profit on (i-1)th // day by resting and profit // on (i-1)th day by selling. rest[i] = Math.max(rest[i - 1], sold[i - 1]); // max of profit by resting // on ith day and // buying on ith day. hold[i] = Math.max(hold[i - 1], rest[i - 1] - prices[i]); // max of profit by selling // on ith day sold[i] = hold[i - 1] + prices[i]; } // maxprofit return Math.max(rest[n - 1], sold[n - 1]);}// Driver Codelet price = [ 2, 4, 5, 0, 2 ];let n = price.length;document.write( maxProfit(price, n),'<br>'); </script> |
Output
4
Time Complexity: O(N)
Auxiliary Space: O(N)
Recursive Approach:
Everyday, We have two choices : Buy/Sell this stock OR ignore and move to the next one.
Along with day, we also need to maintain a buy variable which will tell us that if we want
to do a transaction today it will be of which type (Buy or Sell) and According to that we will
make recursive calls and calculate the answer
C++
// C++ program for the above problem#include <bits/stdc++.h>using namespace std;int f(int idx, int buy, int prices[], int n){ if (idx >= n) { return 0; } int profit = 0; // you can either buy or not buy if (buy == 0) { profit = max(-prices[idx] + f(idx + 1, 1, prices, n), f(idx + 1, 0, prices, n)); } // you can either sell or not sell else { profit = max(prices[idx] + f(idx + 2, 0, prices, n), f(idx + 1, 1, prices, n)); } return profit;}int maxProfit(int prices[], int n){ return f(0, 0, prices, n);}// Driver Codeint main(){ int price[] = { 2, 4, 5, 0, 2 }; int n = sizeof(price) / sizeof(price[0]); cout << maxProfit(price, n) << endl; return 0;} |
Java
// Java program for the above approachpublic class Main { public static int f(int idx, int buy, int[] prices, int n) { if (idx >= n) { return 0; } int profit = 0; // you can either buy or not buy if (buy == 0) { profit = Math.max(-prices[idx] + f(idx + 1, 1, prices, n), f(idx + 1, 0, prices, n)); } // you can either sell or not sell else { profit = Math.max(prices[idx] + f(idx + 2, 0, prices, n), f(idx + 1, 1, prices, n)); } // returning the profit return profit; } // MaxProfit function to call the f() func. public static int maxProfit(int[] prices, int n) { return f(0, 0, prices, n); } // Driver Code public static void main(String[] args) { int[] price = { 2, 4, 5, 0, 2 }; int n = price.length; System.out.println(maxProfit(price, n)); }} |
Python3
# Python program for the above problemdef f(idx, buy, prices, n): if idx >= n: return 0 profit = 0 # you can either buy or not buy if buy == 0: profit = max(-prices[idx] + f(idx + 1, 1, prices, n), f(idx + 1, 0, prices, n)) # you can either sell or not sell else: profit = max(prices[idx] + f(idx + 2, 0, prices, n), f(idx + 1, 1, prices, n)) #returning the profit return profit # MaxProfit function to call the f() func.def maxProfit(prices, n): return f(0, 0, prices, n)# Driver Codeprice = [2, 4, 5, 0, 2]n = len(price)print(maxProfit(price, n)) |
C#
// C# code addition using System;public class MainClass { public static int f(int idx, int buy, int[] prices, int n) { if (idx >= n) { return 0; } int profit = 0; // you can either buy or not buy if (buy == 0) { profit = Math.Max(-prices[idx] + f(idx + 1, 1, prices, n), f(idx + 1, 0, prices, n)); } // you can either sell or not sell else { profit = Math.Max(prices[idx] + f(idx + 2, 0, prices, n), f(idx + 1, 1, prices, n)); } // returning the profit return profit; } // MaxProfit function to call the f() func. public static int maxProfit(int[] prices, int n) { return f(0, 0, prices, n); } // Driver Code public static void Main() { int[] price = { 2, 4, 5, 0, 2 }; int n = price.Length; Console.WriteLine(maxProfit(price, n)); }}// The code is contributed by Arushi Goel. |
Javascript
// JavaScript program for the above problemfunction f(idx, buy, prices, n) {if (idx >= n) {return 0;}let profit = 0;// you can either buy or not buyif (buy == 0) { profit = Math.max(-prices[idx] + f(idx + 1, 1, prices, n), f(idx + 1, 0, prices, n));}// you can either sell or not sellelse { profit = Math.max(prices[idx] + f(idx + 2, 0, prices, n), f(idx + 1, 1, prices, n));}return profit;}function maxProfit(prices, n) {return f(0, 0, prices, n);}// Driver Codeconst price = [2, 4, 5, 0, 2];const n = price.length;console.log(maxProfit(price, n)); |
Output
4
Time Complexity : O(2^N)
Auxiliary Space : O(N)
Memoization DP Approach:
One more way we can approach this problem is by considering buying and selling as two different states of the dp.
C++
// C++ program for the above problem#include <bits/stdc++.h>using namespace std;int f(int idx, int buy, int prices[], vector<vector<int> >& dp, int n){ if (idx >= n) { return 0; } if (dp[idx][buy] != -1) { return dp[idx][buy]; } int profit = 0; // you can either buy or not buy if (buy == 0) { dp[idx][buy] = profit = max( -prices[idx] + f(idx + 1, 1, prices, dp, n), f(idx + 1, 0, prices, dp, n)); } // you can either sell or not sell else { dp[idx][buy] = profit = max( prices[idx] + f(idx + 2, 0, prices, dp, n), f(idx + 1, 1, prices, dp, n)); } return profit;}int maxProfit(int prices[], int n){ vector<vector<int> > dp(n, vector<int>(2, -1)); return f(0, 0, prices, dp, n);}// Driver Codeint main(){ int price[] = { 2, 4, 5, 0, 2 }; int n = sizeof(price) / sizeof(price[0]); cout << maxProfit(price, n) << endl; return 0;} |
Java
import java.util.*;public class Main { // Recursive function to calculate profit static int f(int idx, int buy, int[] prices, List<List<Integer> > dp, int n) { if (idx >= n) { return 0; } if (dp.get(idx).get(buy) != -1) { return dp.get(idx).get(buy); } int profit = 0; // you can either buy or not buy if (buy == 0) { dp.get(idx).set( buy, profit = Math.max( -prices[idx] + f(idx + 1, 1, prices, dp, n), f(idx + 1, 0, prices, dp, n))); } // you can either sell or not sell else { dp.get(idx).set( buy, profit = Math.max( prices[idx] + f(idx + 2, 0, prices, dp, n), f(idx + 1, 1, prices, dp, n))); } return profit; } // Function to calcutate max Profit static int maxProfit(int[] prices, int n) { List<List<Integer> > dp = new ArrayList<>(); for (int i = 0; i < n; i++) { dp.add(new ArrayList<>(Arrays.asList(-1, -1))); } return f(0, 0, prices, dp, n); } // Driver Code public static void main(String[] args) { int[] price = { 2, 4, 5, 0, 2 }; int n = price.length; System.out.println(maxProfit(price, n)); }} |
Python3
from typing import List# Recursive function to calculate profitdef f(idx: int, buy: int, prices: List[int], dp: List[List[int]], n: int) -> int: if idx >= n: return 0 if dp[idx][buy] != -1: return dp[idx][buy] profit = 0 # you can either buy or not buy if buy == 0: dp[idx][buy] = profit = max(-prices[idx] + f(idx + 1, 1, prices, dp, n), f(idx + 1, 0, prices, dp, n)) # you can either sell or not sell else: dp[idx][buy] = profit = max(prices[idx] + f(idx + 2, 0, prices, dp, n), f(idx + 1, 1, prices, dp, n)) return profit# Function to calcutate max Profitdef maxProfit(prices: List[int], n: int) -> int: dp = [[-1, -1] for i in range(n)] return f(0, 0, prices, dp, n)# Driver Codeif __name__ == '__main__': price = [2, 4, 5, 0, 2] n = len(price) print(maxProfit(price, n)) |
C#
using System;class GFG{ static int F(int idx, int buy, int[] prices, int[][] dp, int n) { if (idx >= n) { return 0; } if (dp[idx][buy] != -1) { return dp[idx][buy]; } int profit = 0; // You can either buy or not buy if (buy == 0) { dp[idx][buy] = profit = Math.Max( -prices[idx] + F(idx + 1, 1, prices, dp, n), F(idx + 1, 0, prices, dp, n)); } // You can either sell or not sell else { dp[idx][buy] = profit = Math.Max( prices[idx] + F(idx + 2, 0, prices, dp, n), F(idx + 1, 1, prices, dp, n)); } return profit; } static int MaxProfit(int[] prices, int n) { int[][] dp = new int[n][]; for (int i = 0; i < n; i++) { dp[i] = new int[2]; dp[i][0] = dp[i][1] = -1; } return F(0, 0, prices, dp, n); } static void Main() { int[] price = { 2, 4, 5, 0, 2 }; int n = price.Length; Console.WriteLine(MaxProfit(price, n)); }} |
Javascript
function maxProfit(prices) { const n = prices.length; const dp = new Array(n).fill().map(() => new Array(2).fill(-1)); function f(idx, buy) { if (idx >= n) { return 0; } if (dp[idx][buy] !== -1) { return dp[idx][buy]; } let profit = 0; // you can either buy or not buy if (buy === 0) { dp[idx][buy] = profit = Math.max( -prices[idx] + f(idx + 1, 1), f(idx + 1, 0) ); } // you can either sell or not sell else { dp[idx][buy] = profit = Math.max( prices[idx] + f(idx + 2, 0), f(idx + 1, 1) ); } return profit; } return f(0, 0);}// Driver Codeconst price = [2, 4, 5, 0, 2];console.log(maxProfit(price));//Above code added by Avinash Wani |
Output
4
Time Complexity : O(N)
Auxiliary Space : O(N)
One Pass Method:
Steps:
- First, Initialize the variables for buying, selling, and their previous values.
- second, traverse the array and compute the max profit that can be made by buying and selling the stocks.
- Stores the previous value of buy before it is updated.
- Compute the max profit that can be made by buying the stock on the current day or not buying it.
- Again, store the previous value of sell before it is updated.
- Compute the max profit that can be made by selling the stock on the current day or not selling it.
- last return the max profit.
Below is code implementation for the above approach:
C++
// C++ implementation by using the one-pass method#include <bits/stdc++.h>using namespace std;int maxProfit(int arr[], int n) { // Initialize the variables int buy = INT_MIN, prev_sell = 0, sell = 0, prev_buy; for(int i = 0; i < n; i++) { prev_buy = buy; buy = max(prev_sell - arr[i], prev_buy); prev_sell = sell; sell = max(prev_buy + arr[i], prev_sell); } // Return the maximum profit return sell;}// Driver Codeint main() { int arr[] = {2, 4, 5, 0, 2}; int n = sizeof(arr) / sizeof(arr[0]); cout << maxProfit(arr, n) << endl; return 0;} |
Java
public class Main { // Function to find the maximum profit that can be obtained from buying and selling stocks public static int maxProfit(int[] prices) { int buy = Integer.MIN_VALUE; // Initialize buy with a minimal value, representing no stocks bought int prevSell = 0; // Initialize previous sell with zero profit int sell = 0; // Initialize sell with zero profit int prevBuy; // Variable to store the previous buy value for (int price : prices) { prevBuy = buy; // Store the previous buy value before updating it // Calculate the new buy value, considering either the previous sell or the previous buy buy = Math.max(prevSell - price, prevBuy); prevSell = sell; // Store the previous sell value before updating it // Calculate the new sell value, considering either the previous buy or the previous sell sell = Math.max(prevBuy + price, prevSell); } return sell; // Return the maximum profit after all iterations } public static void main(String[] args) { int[] prices = {2, 4, 5, 0, 2}; System.out.println(maxProfit(prices)); // Print the maximum profit }} |
C#
using System;class MainClass { // Function to find the maximum profit that can be obtained from buying and selling stocks public static int MaxProfit(int[] prices) { int buy = int.MinValue; // Initialize buy with a minimal value, representing no stocks bought int prevSell = 0; // Initialize previous sell with zero profit int sell = 0; // Initialize sell with zero profit int prevBuy; // Variable to store the previous buy value foreach (int price in prices) { prevBuy = buy; // Store the previous buy value before updating it // Calculate the new buy value, considering either the previous sell or the previous buy buy = Math.Max(prevSell - price, prevBuy); prevSell = sell; // Store the previous sell value before updating it // Calculate the new sell value, considering either the previous buy or the previous sell sell = Math.Max(prevBuy + price, prevSell); } return sell; // Return the maximum profit after all iterations } public static void Main (string[] args) { int[] prices = {2, 4, 5, 0, 2}; Console.WriteLine(MaxProfit(prices)); // Print the maximum profit }} |
Output
4
Time Complexity: O(n) because it performs a single pass over the input array of size n.
Auxiliary Space: O(1)
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!
