Best Time to Buy and Sell Stock III

Best time to buy and sell stock iii caps the number of transactions at two, sitting between the single-transaction original and the unlimited version. That cap is what makes it Hard — the greedy no longer applies, and a transaction count must be carried. The direct approach tracks four states, each representing how far through the two transactions you are: - First buy, first sell, second buy, second sell — a share is bought, sold, bought again, and sold again, in that order. Each state is the best balance achievable at that stage. firstBuy is the balance after one purchase, so it is negative. firstSell is the balance after one completed transaction. secondBuy is the balance after buying again out of the first sale's proceeds. secondSell is the final answer. What makes this correct is that each state builds on the one before it: secondBuy = max(secondBuy, firstSell − price) funds the second purchase from the profit already banked. That chaining is what enforces the ordering — the second transaction cannot begin before the first has finished. Updating all four in a single pass, in order, works even though later states read values updated earlier in the same iteration. Allowing a same-day sell and rebuy is harmless, since it produces a net-zero pair that never beats the alternative. Initialise both buy states to negative infinity — or firstBuy to −prices[0] — so an unfilled state never looks profitable. An alternative splits the array at every index, computing the best profit before and after each split point in two passes. Same O(n), and a useful cross-check.

Four states chained in sequence: buy1 → sell1 → buy2 → sell2. Each one feeds the next, and updating them in that order within a single loop means the second transaction's purchase already sees the first sale's profit — the chaining does the bookkeeping.