9.10 State Machine DP

Demo: Best Time to Buy and Sell Stock with Cooldown — LC 309 (Medium — Meta/Google High)

Statement (Demo): Given daily prices, return the maximum profit from any number of buy/sell transactions, with a one-day cooldown: you cannot buy on the day right after you sell. Example: prices=[1,2,3,0,2] → 3 (buy, sell, cooldown, buy, sell) | ⚡ prices.length ≤ 5000

Approach: Three states: hold (holding a share), sold (sold today), rest (empty-handed, cooldown over). Update all three each day — buying is only possible from rest.

function maxProfit(prices) {
  let hold = -Infinity,
    sold = 0,
    rest = 0;
  for (const p of prices) {
    const prevSold = sold;
    sold = hold + p; // sell today
    hold = Math.max(hold, rest - p); // keep holding / buy today
    rest = Math.max(rest, prevSold); // wait (cooldown ends)
  }
  return Math.max(sold, rest);
}

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