Best Time to Buy and Sell Stock with Cooldown medium

Problem Statement

You are given an array prices where prices[i] is the price of a given stock on the i^th day.

Find the maximum profit you can achieve. You may complete as many transactions as you like (buy one and sell one share of the stock multiple times) with the following restrictions:

• After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day).

Example 1:

Input: prices = [1,2,3,0,2] Output: 3 Explanation: transactions = [buy, sell, cooldown, buy, sell]

Example 2:

Input: prices = [1] Output: 0

Steps

This problem can be solved using dynamic programming. We need to maintain three states for each day:

• buy: The maximum profit if we buy the stock on the current day.
• sell: The maximum profit if we sell the stock on the current day.
• cooldown: The maximum profit if we are in a cooldown period on the current day.

We initialize buy to -prices[0] (buying on day 0), sell to 0 (no profit yet), and cooldown to 0 (no profit yet).

Then, we iterate through the prices array:

1. buy[i]: The maximum profit we can get by buying on day i is either the profit from the previous day (buy[i-1]) or the profit from selling two days ago minus the price today (sell[i-2] - prices[i]). We choose the maximum of these.

2. sell[i]: The maximum profit we can get by selling on day i is the profit from buying on the previous day plus the price today (buy[i-1] + prices[i]).

3. cooldown[i]: The maximum profit if we are in the cooldown period on day i is the maximum of the previous day's profit (cooldown[i-1]) and the previous day's selling profit (sell[i-1]). This is because we either continue cooldown or transition from a sell state into a cooldown state.

Finally, the maximum profit will be the maximum of sell[n-1] and cooldown[n-1] (where n is the number of days).

Explanation

The dynamic programming approach cleverly tracks the optimal profit at each step, considering the cooldown constraint. The three state variables allow us to efficiently consider all possible buying, selling, and cooldown scenarios without redundant calculations. The algorithm builds up the optimal solution from smaller subproblems, ensuring the final result is the maximum possible profit.

Code

public class Solution {
    public int MaxProfit(int[] prices) {
        if (prices == null || prices.Length < 2) return 0;

        int n = prices.Length;
        int[] buy = new int[n];
        int[] sell = new int[n];
        int[] cooldown = new int[n];

        buy[0] = -prices[0];
        sell[0] = 0;
        cooldown[0] = 0;

        for (int i = 1; i < n; i++) {
            buy[i] = Math.Max(buy[i - 1], (i >= 2 ? sell[i - 2] : 0) - prices[i]);
            sell[i] = buy[i - 1] + prices[i];
            cooldown[i] = Math.Max(cooldown[i - 1], sell[i - 1]);
        }

        return Math.Max(sell[n - 1], cooldown[n - 1]);
    }
}

Complexity

• Time Complexity: O(n), where n is the number of days. We iterate through the prices array once.
• Space Complexity: O(n), due to the three arrays buy, sell, and cooldown. This could be optimized to O(1) by only using three variables to track the current and previous states instead of full arrays. This optimization is left as an exercise for the reader.