14.19 Best Time to Buy and Sell Stock with Cooldown

14.19.1 Problem Metadata

14.19.2 Description

You may complete multiple transactions, but after selling a stock you must wait one day (cooldown) before buying again. Return the maximum profit.

14.19.3 Examples

Input: [1,2,3,0,2]
Output: 3

14.19.4 Constraints

  • 1 <= prices.length <= 5000

14.19.5 Solution - State Machine DP

14.19.5.1 Walkthrough

This solution uses a state machine dynamic programming approach to handle the cooldown constraint.

Core Strategy:

Unlike Stock II (unlimited transactions, no cooldown), the cooldown rule creates dependencies between transactions. We cannot use the greedy approach because selling today affects when we can buy next.

The key insight is to model this as a finite state machine with three states:

  1. hold: Currently holding a stock (profit if we’re in this state)
  2. sold: Just sold a stock today (profit from selling)
  3. rest: Resting or in cooldown (profit while not holding)

State Transitions:

     buy
rest ───→ hold
 ↑         │
 │   sell │
 └─────────┘
   (cooldown)

At each day, we can transition between states: - To reach hold: Either keep holding, OR buy from rest (can’t buy from sold due to cooldown) - To reach sold: Sell from hold - To reach rest: Either keep resting, OR enter cooldown from sold

Recurrence Relations:

For each day i:

hold[i] = max(hold[i-1], rest[i-1] - price[i])
          ↑              ↑
          keep holding   buy today from rest state

sold[i] = hold[i-1] + price[i]
          ↑
          sell from hold state

rest[i] = max(rest[i-1], sold[i-1])
          ↑              ↑
          keep resting   enter cooldown after selling

Why This is Dynamic Programming: - Overlapping subproblems: Each day’s optimal state depends on previous day’s states - Optimal substructure: Optimal profit at day i builds on optimal profits from day i-1 - State dependencies: Cannot make greedy local choices due to cooldown constraint

Visual Example Walkthrough:

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

Day 0: price=1
  hold = -1  (buy at 1)
  sold = 0   (can't sell on first day)
  rest = 0   (start in rest state)

Day 1: price=2
  hold = max(-1, 0-2) = -1  (keep holding from day 0)
  sold = -1 + 2 = 1         (sell, profit = 1)
  rest = max(0, 0) = 0      (no sold state yet to enter cooldown)

Day 2: price=3
  hold = max(-1, 0-3) = -1  (keep holding)
  sold = -1 + 3 = 2         (sell from hold, profit = 2)
  rest = max(0, 1) = 1      (enter cooldown after day 1 sell)

Day 3: price=0
  hold = max(-1, 1-0) = 1   (buy at 0 from rest, profit = 1) ✓
  sold = -1 + 0 = -1        (selling at 0 is bad)
  rest = max(1, 2) = 2      (enter cooldown after day 2 sell)

Day 4: price=2
  hold = max(1, 2-2) = 1    (keep holding from day 3)
  sold = 1 + 2 = 3          (sell at 2, total profit = 3) ✓
  rest = max(2, -1) = 2     (cooldown or rest)

Result: max(sold, rest) = max(3, 2) = 3
Optimal strategy: Buy@1, Sell@2, Cooldown, Buy@0, Sell@2

Key Insight: Why Greedy Fails Here

Unlike Stock II, we cannot greedily capture every price increase: - 1→2→3 sequence: Greedy would sell at 2 and buy at 2, but cooldown prevents this - Must consider future opportunities when deciding to sell today - DP tracks all possible states to find the optimal sequence of transactions

Space Optimization:

Notice we only need the previous day’s states, so we use three variables instead of arrays (O(1) space).

14.19.5.2 Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(1)

14.19.5.3 Implementation Steps

  1. Initialize hold = -prices[0], sold = 0, rest = 0.
  2. For each subsequent price:
    • int prevSold = sold;
    • sold = hold + price;
    • hold = Math.max(hold, rest - price);
    • rest = Math.max(rest, prevSold);
  3. Return Math.max(sold, rest).

14.19.5.4 Code - Java

public int maxProfit(int[] prices) {
    int hold = -prices[0];
    int sold = 0;
    int rest = 0;

    for (int i = 1; i < prices.length; i++) {
        int prevSold = sold;
        sold = hold + prices[i];
        hold = Math.max(hold, rest - prices[i]);
        rest = Math.max(rest, prevSold);
    }

    return Math.max(sold, rest);
}