prices[i] is the price of one share on day i. A trade is buying one share and selling it on a later day; its profit is the selling price minus the buying price. You may make at most two trades, and you hold at most one share at a time, so the first share must be sold before the second is bought. Selling one share and buying the next on the same day is allowed.
Write max_profit_two_trades(prices: list[int]) -> int that returns the largest total profit. Making no trade at all earns 0.
max_profit_two_trades([2, 8, 4, 10]) # 12 buy 2, sell 8, buy 4, sell 10
One trade could only make 8 (buy 2, sell 10). Two trades skip the dip to 4 and make 6 + 6.
max_profit_two_trades([6, 1, 3, 2, 8, 4, 9]) # 12 buy 1, sell 8, buy 4, sell 9
There are three rises (1 to 3, 2 to 8, 4 to 9), but only two trades. The best plan joins the first two into one trade, 1 to 8, and keeps 4 to 9: 7 + 5 = 12. Keeping the two biggest rises as they are only makes 6 + 5 = 11.
max_profit_two_trades([9, 7, 7, 4]) # 0 the price never goes up
Constraints: 0 <= len(prices) <= 10^5, 0 <= prices[i] <= 10^4.
⭐ Bonus: a speed test with 100,000 days earns a star in O(n) time. Trying every split of the days into "first trade" and "second trade" and solving each side from scratch is O(n²), which is too slow there.
Show hint
At any moment you're in one of four situations: holding your first share, done with one trade, holding your second share, or done with two. Keep the best cash for each one, day by day.