Best two non-overlapping trades
Asked at DE Shaw, Millennium
Given daily prices, you may complete at most two buy-then-sell trades, and the second buy must occur at or after the first sell (no overlapping positions).
prices = [3, 3, 5, 0, 0, 3, 1, 4]
-> 6 # trade 1: buy 0 (idx 3), sell 3 (idx 5) -> +3
# trade 2: buy 1 (idx 6), sell 4 (idx 7) -> +3
Return the maximum total profit. Aim for .
Show a hint
If you knew the day separating trade one from trade two, the problem would split into two independent single-trade problems. Can you precompute one side for all split points?
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.