Best profit with at most two trades

Question

Given daily prices, complete at most two buy-then-sell trades (you must sell before buying again) to maximize total profit. Return the maximum profit. Aim for O(n) time, O(1) space.

Accepted Answer

With the cap fixed at two, you can name all four states explicitly instead of looping over transaction counts: - buy1, best balance after opening the first position (negative, you paid for a share). - sell1, best profit after closing the first trade. - buy2, best balance after opening the second position, funded by sell1. - sell2, best profit after closing the second trade. Update all four each day at price p: 	ext{buy1} = \max(	ext{buy1}, -p), \quad 	ext{sell1} = \max(	ext{sell1}, 	ext{buy1} + p), 	ext{buy2} = \max(	ext{buy2}, 	ext{sell1} - p), \quad 	ext{sell2} = \max(	ext{sell2},…

Best profit with at most two trades

Your answer

More Coding questions