309. Best Time to Buy and Sell Stock with Cooldown

Time: O(n)

Space: O(1)

Intuition

Three states: "held" (have stock), "sold" (just sold, in cooldown), "rest" (no stock, no cooldown). Transitions: held = max(prev_held, prev_rest - price). sold = prev_held + price. rest = max(prev_rest, prev_sold). Only need the previous day's three values.

Algorithm

1held = -INF, sold = 0, rest = 0.
2For each price: newHeld = max(held, rest - price). newSold = held + price. newRest = max(rest, sold).
3held=newHeld, sold=newSold, rest=newRest.
4Return max(sold, rest).

Example Walkthrough

Input: prices = [1,2,3,0,2]

1.p=1: held=max(-Infinity,0-1)=-1, sold=-Infinity, rest=0.
2.p=2: held=max(-1,0-2)=-1, sold=-1+2=1, rest=0.
3.p=3: held=max(-1,0-3)=-1, sold=-1+3=2, rest=max(0,1)=1.
4.p=0: held=max(-1,1-0)=1, sold=-1+0=-1, rest=max(1,2)=2.
5.p=2: held=max(1,2-2)=1, sold=1+2=3, rest=max(2,-1)=2.
6.Return max(3,2)=3.

Output: 3

Common Pitfalls

•Update all three states simultaneously (from previous values) - do not read updated values mid-step.

309.cs

// Approach: State-machine DP with three states tracked as rolling variables.
// 'held' = max profit when holding a stock; 'sold' = profit the day we just sold (now in cooldown);
// 'rest' = profit while not holding and not in cooldown (free to buy).
// Transitions each day: held = max(held, rest - price); sold = held + price; rest = max(rest, sold).
// Rolling variables replace an n x 3 table, giving O(1) space.
// Time: O(n) Space: O(1)

public class Solution
{
    public int MaxProfit(int[] prices)
    {
        int n = prices.Length;
        // int[][] dp = new int[n][];
        // for(int i = 0; i < n; i++)
        // {
        //     int[] arr = new int[2];
        //     Array.Fill(arr, -1);
        //     dp[i] = arr;
        // }

        // return topDown(0, 1, prices, dp);
        return tabulation(n, prices);
    }

    private int topDown(int ind, int canBuy, int[] prices, int[][] dp)
    {
        if (ind >= prices.Length)
            return 0;

        if (dp[ind][canBuy] != -1)
            return dp[ind][canBuy];

        int profit = 0;
        if (canBuy == 1)
        {
            int bought = -prices[ind] + topDown(ind + 1, 0, prices, dp);
            int notBought = topDown(ind + 1, 1, prices, dp);
            profit = Math.Max(bought, notBought);
        }
        else
        {
            int sold = prices[ind] + topDown(ind + 2, 1, prices, dp);
            int notSold = topDown(ind + 1, 0, prices, dp);
            profit = Math.Max(sold, notSold);
        }

        return dp[ind][canBuy] = profit;
    }

    private int tabulation(int n, int[] prices)
    {
        int[][] dp = new int[n + 2][];
        for (int i = 0; i <= n + 1; i++)
        {
            int[] arr = new int[2];
            dp[i] = arr;
        }

        for (int ind = n - 1; ind >= 0; ind--)
        {
            for (int canBuy = 0; canBuy <= 1; canBuy++)
            {
                int profit = 0;
                if (canBuy == 1)
                {
                    int bought = -prices[ind] + dp[ind + 1][0];
                    int notBought = dp[ind + 1][1];
                    profit = Math.Max(bought, notBought);
                }
                else
                {
                    int sold = prices[ind] + dp[ind + 2][1];
                    int notSold = dp[ind + 1][0];
                    profit = Math.Max(sold, notSold);
                }
                dp[ind][canBuy] = profit;
            }
        }

        return dp[0][1];
    }
}

Was this solution helpful?