Given the prices of stock for n number of days. Every ith day tell the price of the stock on that day. Find the maximum profit that you can make by buying and selling stock with the restriction of after you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).
Examples:
Input: arr[] = {1, 2, 3, 0, 2}
Output : 3
Explanation: You first buy on day 1, sell on day 2 then cool down, then buy on day 4, and sell on day 5. The total profit earned is (2-1) + (2-0) = 3, which is the maximum achievable profit.Input: arr[] = {3, 1, 6, 1, 2, 4}
Output: 7
Explanation: You first buy on day 2 and sell on day 3 then cool down, then again you buy on day 5 and then sell on day 6. Clearly, the total profit earned is (6-1) + (4-2) = 7, which is the maximum achievable profit.
Approach: This can be solved with the following idea:
We need to maintain three states for each day. The first stage will be maxed profit we can make if we have one stock yet to be sold. The second stage will be the max profit we can make if we have no stock left to be sold. The third state is the cooldown state. It is similar to the second state, but we have completed the cooldown of 1 day after selling the stock. Each state can be maintained using a DP vector.
The following approach is implemented below:
C++
// C++ program to maximize profit by // buying and selling stock // with cooldown #include <bits/stdc++.h> using namespace std; // Function to find maximum profit long long maximumProfit(vector< int >& v, int n) { vector<vector< long long > > dp(v.size() + 1, vector< long long >(3)); dp[0][0] = -v[0]; for ( int i = 1; i <= n; i++) { // Maximum of buy state profit // till previous day or buying a // new stock with cooldown state // of previous day dp[i][0] = max(dp[i - 1][0], dp[i - 1][2] - v[i]); // Maximum of sold state profit // till previous day or selling // the stock on current day with // buy state of previous day dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + v[i]); // Sold state of previous day dp[i][2] = dp[i - 1][1]; } // Return Sold state profit /// of final day return dp[n - 1][1]; } // Driver code int main() { vector< int > v = { 1, 2, 3, 0, 2 }; // Function call cout << maximumProfit(v, v.size()); return 0; } |
Java
// Java program to maximize profit by buying and selling stock with cooldown import java.util.Arrays; public class GFG { public static long maximumProfit( int [] v, int n) { long [][] dp = new long [n][ 3 ]; dp[ 0 ][ 0 ] = -v[ 0 ]; for ( int i = 1 ; i < n; i++) { // Maximum of buy state profit till previous day or // buying a new stock with cooldown state of previous day dp[i][ 0 ] = Math.max(dp[i - 1 ][ 0 ], dp[i - 1 ][ 2 ] - v[i]); // Maximum of sold state profit till previous day or // selling the stock on current day with buy state of previous day dp[i][ 1 ] = Math.max(dp[i - 1 ][ 1 ], dp[i - 1 ][ 0 ] + v[i]); // Sold state of previous day dp[i][ 2 ] = dp[i - 1 ][ 1 ]; } // return Sold state profit of final day return dp[n - 1 ][ 1 ]; } public static void main(String[] args) { int [] v = { 1 , 2 , 3 , 0 , 2 }; System.out.println(maximumProfit(v, v.length)); } } // This code is contributed by Shikhar Reyya |
Python3
# Python program to maximize profit by buying and selling stock with cooldown def maximumProfit(v): n = len (v) dp = [[ 0 , 0 , 0 ] for _ in range (n + 1 )] dp[ 0 ][ 0 ] = - v[ 0 ] for i in range ( 1 , n + 1 ): # Maximum of buy state profit till the previous day or # buying a new stock with the cooldown state of the previous day dp[i][ 0 ] = max (dp[i - 1 ][ 0 ], dp[i - 1 ][ 2 ] - v[i - 1 ]) # Maximum of sold state profit till the previous day or # selling the stock on the current day with the buy state of the previous day dp[i][ 1 ] = max (dp[i - 1 ][ 1 ], dp[i - 1 ][ 0 ] + v[i - 1 ]) # Sold state of the previous day dp[i][ 2 ] = dp[i - 1 ][ 1 ] # Return the sold state profit of the final day return dp[n][ 1 ] v = [ 1 , 2 , 3 , 0 , 2 ] print (maximumProfit(v)) # This code is contributed by Shikhar Reyya |
C#
// C# program to maximize profit by buying and selling stock with cooldown using System; using System.Collections.Generic; public class GFG { static long MaximumProfit(List< int > v, int n) { List<List< long > > dp = new List<List< long > >(); // Initialize the dp list with initial values of 0 for ( int i = 0; i <= n; i++) { dp.Add( new List< long >{ 0, 0, 0 }); } dp[0][0] = -v[0]; for ( int i = 1; i <= n; i++) { // Maximum of buy state profit till the previous // day or buying a new stock with the cooldown // state of the previous day dp[i][0] = Math.Max(dp[i - 1][0], dp[i - 1][2] - v[i - 1]); // Maximum of sold state profit till the // previous day or selling the stock on the // current day with the buy state of the // previous day dp[i][1] = Math.Max(dp[i - 1][1], dp[i - 1][0] + v[i - 1]); // Sold state of the previous day dp[i][2] = dp[i - 1][1]; } // Return the sold state profit of the final day return dp[n][1]; } static void Main( string [] args) { List< int > v = new List< int >{ 1, 2, 3, 0, 2 }; Console.WriteLine(MaximumProfit(v, v.Count)); } } // This code is contributed by Shikhar Reyya |
Javascript
// Javascript program to maximize profit by buying and // selling stock with cooldown function maximumProfit(v) { var n = v.length; var dp = new Array(n + 1); for ( var i = 0; i < n + 1; i++) { dp[i] = new Array(3); for ( var j = 0; j < 3; j++) { dp[i][j] = 0; } } dp[0][0] = -v[0]; for ( var i = 1; i <= n; i++) { // Maximum of buy state profit till the previous day or // buying a new stock with the cooldown state of the previous day dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2] - v[i - 1]); // Maximum of sold state profit till the previous day or // selling the stock on the current day with the buy state // of the previous day dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + v[i - 1]); // Sold state of the previous day dp[i][2] = dp[i - 1][1]; } // Return the sold state profit of the final day return dp[n][1]; } var v = [1, 2, 3, 0, 2]; console.log(maximumProfit(v)); // This code is contributed by Tapesh(tapeshdua420) |
3
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!