codejump
MediumPro challengePythonJavaScriptTypeScript

DP — Best Time to Buy and Sell Stock With Cooldown

AlgorithmsDynamic ProgrammingState Machine

solve(prices) — prices[i] is the price of a stock on day i. You may complete
as many transactions as you like (buy one, sell one, repeat), with two rules: you
hold at most one share at a time, and **after you sell you cannot buy the next
day** (one day of cooldown). Return the maximum profit.

Model it as a small state machine and carry the best profit for each state:
*holding* a share, *just sold* today, or *resting* with nothing (free to buy).

Examples

solve([1,2,3,0,2])    → 3     // buy 1, sell 2, cooldown, buy 0, sell 2
solve([1])            → 0
solve([1,2,4])        → 3
solve([6,1,3,2,4,7])  → 6

Sample tests

Test #1Classic example
Input: [[1,2,3,0,2]]
Output: 3
Test #2One day
Input: [[1]]
Output: 0
Test #3Single long hold
Input: [[1,2,4]]
Output: 3