Best Time to Buy and Sell Stock with Cooldown

Examples

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

Buy at 1, sell at 2 (profit 1), cooldown, buy at 0, sell at 2 (profit 2). Total: 3.

Input: prices = [1]
Output: 0

There's no second day to sell on, so the best move is to do nothing.

Constraints

• 1 <= prices.length <= 5000

• 0 <= prices[i] <= 1000

Approach

Instead of tracking single "best profit so far," track three separate running totals for each day: the best profit if you're currently holding a share, the best profit if you just sold today, and the best profit if you're resting (free to buy, not in a forced cooldown).

Each day's three values only depend on the previous day's three values: - holding today is either the same as yesterday (do nothing), or you bought today using yesterday's resting profit. - just sold today only makes sense if you were holding yesterday, plus today's price. - resting today is the better of resting yesterday, or having just sold yesterday (the cooldown day has passed).

The final answer is the better of "just sold" and "resting" on the very last day — you'd never want to end while still holding a share.

Solutions

Brute Force — Recursion

At each day, recursively try both choices allowed by the current state (holding or not): do nothing, or buy/sell. Selling jumps two days ahead to account for the cooldown. Correct, but re-explores the same (day, state) pairs over and over.

function maxProfit(prices) {
  const n = prices.length;

  function solve(day, holding) {
    if (day >= n) return 0;

    let best = solve(day + 1, holding); // do nothing today

    if (holding) {
      best = Math.max(best, prices[day] + solve(day + 2, false)); // sell, then cooldown tomorrow
    } else {
      best = Math.max(best, -prices[day] + solve(day + 1, true)); // buy
    }

    return best;
  }

  return solve(0, false);
}

Time: O(2^n) · Space: O(n) — recursion depth

Optimal — Bottom-Up 2D Table

Build a table with one row per day and three columns — holding, just sold, and resting — where each day's row is computed purely from the previous day's row.

function maxProfit(prices) {
  const n = prices.length;
  if (n === 0) return 0;

  const HOLD = 0, SOLD = 1, REST = 2;
  const table = Array.from({ length: n }, () => new Array(3).fill(0));

  table[0][HOLD] = -prices[0];
  table[0][SOLD] = -Infinity; // can't have sold yet on day 0
  table[0][REST] = 0;

  for (let day = 1; day < n; day++) {
    table[day][HOLD] = Math.max(table[day - 1][HOLD], table[day - 1][REST] - prices[day]);
    table[day][SOLD] = table[day - 1][HOLD] + prices[day];
    table[day][REST] = Math.max(table[day - 1][REST], table[day - 1][SOLD]);
  }

  return Math.max(table[n - 1][SOLD], table[n - 1][REST]);
}

Time: O(n) · Space: O(n) — can be reduced to O(1) by keeping only the previous day's three values