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 of sell 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 be Integer.MIN_VALUE and INT_MIN respectively.
• If you're doing this in Python, it's also okay to use -float('inf') as the initial value for the hold variable.
• Note that in the for loop that iterates over the prices array, we use a temporary variable (cache) to store the value of sell before updating it. This is because the new calculation of hold requires the old sell value that we've just updated. By storing it in cache, 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.