Leetcode 309. Best Time to Buy and Sell Stock with Cooldown
Problem Explanation
In this problem, we are given an array whose ith element represents the price of a specific stock at ith day. We have to make a decision whether we should buy, sell, or cool down on each day to maximize total profit. We could complete as many transactions as we like, but there are two limitations:
- We can't engage in multiple simultaneous transactions - which means we must sell the stock before we buy again.
- After we sell a stock, we can't buy stock on the next day - which means we have to cool off for 1 day.
For example, given prices [1,2,3,0,2], the maximum profit could be achieved by buying on day 1 (price=1), selling on day 2 (price=2), cooling off on day 3 (price=3), buying on day 4 (price=0), and then selling on day 5 (price=2). The maximum profit is 2 - 1 + 2 - 0 = 3.
Solution Approach
The solution is achieved by dynamic programming,.
We keep three variables for each day: sell
, hold
, and prev
.
sell
represents the maximum profit possible if we sell the stock on the current day.hold
represents the max profit possible if we hold the stock on the current day.prev
stores the value ofsell
from the previous day.
In essence, for each day, we either sell the stock and earn the money (making sure to take into account the 1 day cooldown period) or hold the stock and earn no money.
For example, let's consider prices [1,2,3,0,2]:
- On the first day, we can either buy the stock (hold = -prices[0]), or do nothing (sell = 0).
- On the second day, we can either sell the stock we bought on day 1 (sell = hold + prices[1]) or keep holding it (hold = max(hold, prev - prices[1])).
- And so on until we have processed all days.
In the end, the max profit is stored in sell
.
Python Solution
1 2python 3class Solution: 4 def maxProfit(self, prices: List[int]) -> int: 5 # Initialize variables 6 sell, hold, prev = 0, float('-inf'), 0 7 for price in prices: 8 # Update variables for current day 9 prev, sell, hold = sell, max(sell, hold + price), max(hold, prev - price) 10 return sell
Java Solution
1 2java 3class Solution { 4 public int maxProfit(int[] prices) { 5 int sell = 0, hold = Integer.MIN_VALUE, prev = 0; 6 for (int price : prices) { 7 int cache = sell; 8 sell = Math.max(sell, hold + price); 9 hold = Math.max(hold, prev - price); 10 prev = cache; 11 } 12 return sell; 13 } 14}
JavaScript Solution
1 2javascript 3var maxProfit = function(prices) { 4 let sell = 0, hold = -Infinity, prev = 0; 5 for (let price of prices) { 6 let cache = sell; 7 sell = Math.max(sell, hold + price); 8 hold = Math.max(hold, prev - price); 9 prev = cache; 10 } 11 return sell; 12};
C++ Solution
1 2cpp 3class Solution { 4public: 5 int maxProfit(vector<int>& prices) { 6 int sell = 0, hold = INT_MIN, prev = 0; 7 for (int price : prices) { 8 int cache = sell; 9 sell = max(sell, hold + price); 10 hold = max(hold, prev - price); 11 prev = cache; 12 } 13 return sell; 14 } 15};
C# Solution
1 2csharp 3public class Solution { 4 public int MaxProfit(int[] prices) { 5 int sell = 0, hold = Int32.MinValue, prev = 0; 6 foreach (int price in prices) { 7 int cache = sell; 8 sell = Math.Max(sell, hold + price); 9 hold = Math.Max(hold, prev - price); 10 prev = cache; 11 } 12 return sell; 13 } 14}
In all these solutions, for each day, we update sell
, hold
, and prev
taking into consideration the constraints of the problem - that you can't engage in multiple transactions on the same day and you need a cooldown day after selling. The maximum profit is then stored in the sell
variable which we return.All the provided solutions have a time complexity of O(n) because we iterate over the prices array once. The space complexity is O(1) as we use only three variables to keep track of our profits from holding and selling the stock, and the previous day's stock.
Tips for Implementation
- When implementing this solution in your language of choice, make sure to initialize
hold
with the smallest number possible in the language. For Java and C++, that would beInteger.MIN_VALUE
andINT_MIN
respectively. - If you're doing this in Python, it's also okay to use
-float('inf')
as the initial value for thehold
variable. - Note that in the for loop that iterates over the prices array, we use a temporary variable (
cache
) to store the value ofsell
before updating it. This is because the new calculation ofhold
requires the oldsell
value that we've just updated. By storing it incache
, we ensure that we're using the correct value for the calculation. - As we iterate through each day, we calculate if selling or holding gives the maximum profit. If selling results in more profit, then sell is updated, else hold is updated. Finally, the maximum of the two i.e., sell, is returned.
Finally, it's important to note that this problem has been solved with a dynamic programming approach, which isn't an easy concept to grasp. While this solution is efficient, it's perfectly okay if you struggle to understand it. Keep practicing and trying to implement solutions on your own, and you'll gradually get a firmer grasp of dynamic programming. Always remember to break down complex problems like this into smaller parts - like how this problem can be separated into 'days' and 'activities on each day'. This will help you manage and keep track of different variables across iterations, and will make it easier for you to structure your solution algorithms.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.