442. Trading With a Cooldown Day
Prices are given for n consecutive days. You may buy and sell any number of
times but hold at most one unit at a time, and after SELLING you must wait one
full day before buying again. Print the largest total profit.
1 2 3 0 2 -> 3 buy at 1, sell at 2, wait, buy at 0, sell at 2
Without the cooldown the answer is the sum of every rise, which is a one-line greedy. The cooldown breaks that completely: taking a small rise today can forbid a large one tomorrow, so no local rule works.
The repair is to make the state say what you are allowed to do next. Three situations exist at the end of a day:
hold holding one unit
sold sold TODAY, so tomorrow is the forced rest day
rest holding nothing and free to buy
and each transition is then forced:
hold = max(hold, rest - price) keep holding, or buy from a free day
sold = hold + price selling is only possible while holding
rest = max(rest, sold) stay free, or become free after the rest day
The answer is the better of sold and rest on the last day, since holding at the
end is never useful.
All three must be computed from the PREVIOUS day's values. Updating hold first
and then reading it for sold sells on the same day it was bought, which is a
different problem and a larger answer.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ price ≤ 1000000`
Input
The first line contains an integer n.
The second line contains n space-separated prices.
Output
Print the largest total profit obtainable with a one-day cooldown after each sale.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.