Stock Buy and Sell – Max 2 Transactions Allowed

Time: O(n)

Space: O(1)

Intuition

DP with states. Track best profit with at most 2 transactions. Two passes: forward for best single transaction up to day i, backward for best single transaction from day i.

Algorithm

1Forward pass: best1[i] = max profit from single transaction in prices[0..i].
2Backward pass: best2[i] = max profit from single transaction in prices[i..n-1].
3Answer = max(best1[i] + best2[i+1]) for all i.

Common Pitfalls

•Two transactions can share a day boundary. DP states: buy1, sell1, buy2, sell2.

Stock Buy and Sell – Max 2 Transactions Allowed.java

Java

// Approach: DP with states: before first buy, holding first, after first sell, holding second, after second sell.
// Time: O(n) Space: O(1)
class Solution {
    public static int maxProfit(int[] prices) {
        int buy1 = Integer.MIN_VALUE, buy2 = Integer.MIN_VALUE;
        int sell1 = 0, sell2 = 0;

        for (int price : prices) {

            buy1 = Math.max(buy1, -price);
            sell1 = Math.max(sell1, buy1 + price);

            buy2 = Math.max(buy2, sell1 - price);
            sell2 = Math.max(sell2, buy2 + price);
        }

        return sell2;
    }
}

Was this solution helpful?