Max trading profit with a cooldown
Asked at DE Shaw
Given daily prices, you may complete as many buy-then-sell round trips as you like (holding at most one share), but after each sell you must observe a one-day cooldown before buying again.
prices = [1, 2, 3, 0, 2]
-> 3 # buy@1, sell@2, cooldown, buy@0, sell@2
Return the maximum profit. Aim for time, space.
Show a hint
On any evening you are in exactly one of three situations: holding a share, just sold today, or flat and free to buy. Which situations can lead to which?
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.