111. Best Time to Buy and Sell Stock III

Track four running best values as you scan the prices: the best position after the first buy, after the first sell, after the second buy, and after the second sell. Each depends only on the previous state and the current price, so one pass suffices.

Idea

At most two transactions means four events in order: buy1, sell1, buy2, sell2. Track the best achievable balance after each event:

• buy1 = best after buying once = max(buy1, -price).
• sell1 = best after selling once = max(sell1, buy1 + price).
• buy2 = best after buying again (using sell1's profit) = max(buy2, sell1 - price).
• sell2 = best after selling the second = max(sell2, buy2 + price).

Updating them in this order each day lets the second transaction build on the first. sell2 is the answer.

Algorithm

1. buy1 = buy2 = -∞, sell1 = sell2 = 0.
2. For each price, update the four states in order.
3. Return sell2.

Worked example: [3,3,5,0,0,3,1,4]

Buy at 0 (index 3), sell at 3 (index 5) → +3; buy at 1 (index 6), sell at 4 (index 7) → +3. Total 6.

Complexity

• Time: O(n).
• Space: O(1).

class Solution {
    public int maxProfit(int[] prices) {
        int buy1 = Integer.MIN_VALUE, buy2 = Integer.MIN_VALUE;
        int sell1 = 0, sell2 = 0;
        for (int p : prices) {
            buy1 = Math.max(buy1, -p);
            sell1 = Math.max(sell1, buy1 + p);
            buy2 = Math.max(buy2, sell1 - p);
            sell2 = Math.max(sell2, buy2 + p);
        }
        return sell2;
    }
}