123. Best Time to Buy and Sell Stock III
You are given an array prices where prices[i] is the price of a single share on day i.
You may complete at most two trades, where a trade means buying the share on one day and selling it on a later day. The trades cannot overlap: you must finish the first sale before the second purchase, and you can hold at most one share at a time.
Return the largest total profit those (up to) two trades can earn. Using one trade, or none at all, is allowed — if nothing makes money, return 0.
Example 1:
Input: prices = [3, 3, 5, 0, 0, 3, 1, 4]
Output: 6
Explanation: Buy at 0 (day 3) and sell at 3 (day 5) for a profit of 3, then buy at 1 (day 6) and sell at 4 (day 7) for another 3. Total 6.
Example 2:
Input: prices = [1, 2, 3, 4, 5]
Output: 4
Explanation: One trade covering the whole climb (buy at 1, sell at 5) earns 4. Splitting the climb into two trades cannot do better here.
Constraints:
- 1 ≤ prices.length ≤ 10⁵
- 0 ≤ prices[i] ≤ 10⁵
Hints:
Two non-overlapping trades split the timeline: one happens in some prefix of the days, the other in the remaining suffix. What if you knew the best single trade for every prefix and every suffix?
Build `left[i]` = best one-trade profit within days 0..i (a forward sweep) and `right[i]` = best one-trade profit within days i..n-1 (a backward sweep). The answer is the best `left[i] + right[i+1]` split, or a single trade alone.
For O(1) space, run one pass with four running states — money after the 1st buy, 1st sell, 2nd buy, 2nd sell — each maximized from the previous state and today's price.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: prices = [3, 3, 5, 0, 0, 3, 1, 4]
Expected output: 6