444. 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.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ price ≤ 1000000`