267. Best Time to Buy and Sell Stock with Cooldown
You are given an integer array prices, where prices[i] is a stock's price on day i. You may complete as many buy–sell transactions as you like, holding at most one share at a time (you must sell before buying again).
The twist is a cooldown: after you sell, you are locked out for one full day — you cannot buy on the day immediately following a sale. Buying and selling on the same day is not allowed either.
Return the maximum total profit you can achieve. Doing nothing at all is always allowed, so the answer is never negative.
Example 1:
Input: prices = [2, 4, 1, 7]
Output: 6
Explanation: Grabbing the quick +2 (buy day 0, sell day 1) triggers a cooldown on day 2 and strands you afterward with nothing better. The optimum skips it: buy at 1 on day 2, sell at 7 on day 3, profit 6.
Example 2:
Input: prices = [3, 2, 6, 5, 0, 3]
Output: 7
Explanation: Buy at 2 (day 1), sell at 6 (day 2) for +4. Day 3 is the cooldown. Buy at 0 (day 4), sell at 3 (day 5) for +3. Total 7.
Example 3:
Input: prices = [5]
Output: 0
Explanation: With a single day there is no way to buy and later sell, so the best move is no move.
Constraints:
- 1 ≤ prices.length ≤ 5000
- 0 ≤ prices[i] ≤ 1000
Hints:
Greedy pair-picking breaks here: the cooldown means a profitable early trade can poison a better later one. When the value of today's choice depends on what you did yesterday, think dynamic programming with explicit states.
On any day you are in one of three situations: holding a share, having sold today, or free (no share, no fresh sale). Write the best profit for each state as a function of yesterday's three values.
The cooldown is a missing edge in the state machine: a buy may only come from yesterday's *free* state, never from yesterday's *just sold* state. Three rolling variables give O(n) time and O(1) space.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: prices = [2, 4, 1, 7]
Expected output: 6