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]) → 6Sample 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