Best Time to Buy and Sell Stock with Cooldown

Problem

You are given an array prices where prices[i] is the price of a share on day i. You may complete as many buy-then-sell transactions as you want, holding at most one share at a time, with one restriction: after selling a share you must wait one full day before buying again (you cannot buy on the day immediately after a sale). Return the maximum total profit.

• prices holds up to a few thousand daily prices.
• Each price is a non-negative integer, at most a few thousand.

Examples

• prices = [2, 4, 9, 1, 5] → 7. Buy at 2 on day 0, sell at 9 on day 2; selling at 4 first would force a cooldown that forfeits the run up to 9.
• prices = [4] → 0. Nothing to sell to.
• prices = [5, 2] → 0. Falling prices, no profitable trade.

Hints

1. Each day you are in one of a small number of situations: holding a share, just sold, or free to buy. Draw those as states and ask what actions move between them.
2. For each state, the best balance today depends only on the best balances of the states you could have come from yesterday.
3. Three-state DP: hold, sold (must rest today), and rest (free to buy). The cooldown is enforced by only allowing buys from rest, and sold feeds into rest a day later.