At Most Two Trades
Prices are given for n consecutive days. You may complete AT MOST TWO trades,
holding at most one unit at a time and selling before buying again. Print the
largest total profit.
3 3 5 0 0 3 1 4 -> 6 buy 3 sell 5, then buy 0 sell 4
Splitting the array in two and solving each half is a natural instinct and it is
wrong, because the best split point is not known in advance and trying all of them
is O(n^2).
The right state records how far through the pair of trades you are. There are four milestones, and each is the best total achievable having reached it:
buy1 after buying the first time (negative, a cost)
sell1 after selling the first time
buy2 after buying the second time
sell2 after selling the second time
and each is reached from the one before it:
buy1 = max(buy1, -price)
sell1 = max(sell1, buy1 + price)
buy2 = max(buy2, sell1 - price)
sell2 = max(sell2, buy2 + price)
Updating them in that order within a single day is deliberate and correct, unlike
problems 442 and 443. Using today's buy1 to compute today's sell1 means buying
and selling on the same day for zero profit, which is harmless because it can never
beat a real trade, and it lets the chain be written as four lines with no saved
copies.
The answer is sell2, and fewer than two trades is covered automatically, since a
zero-profit second trade is always available.