Dynamic ProgrammingState Machine
You may trade a stock as many times as you like, but you can hold at most one share, and after you sell you must wait one full day (a cooldown day) before buying again. Find the maximum profit given the daily prices.
Input
Line 1: n. Line 2: n prices.
Output
Print the maximum profit.
Constraints
1 <= n <= 5000 0 <= price <= 1000
Example 1
Input
5 1 2 3 0 2
Output
3
Buy 1, sell 2, cool down, buy 0, sell 2: profit 3.