123. Best Time to Buy and Sell Stock III

Intuition

At most two transactions means the trader passes through at most five states in order: nothing, holding the first share, sold it, holding the second share, sold it. Track the best cash balance reachable in each of the four action states, and update all four as each day's price arrives. Cash after a buy is negative (you paid), cash after a sell adds the price back.

The order of the updates within a day matters only in that it lets a later state read the same day's earlier state. That allows buying and selling on the same day, which nets 0 and never changes the optimum, so it is harmless and keeps the code to a single pass with no lookback.

Approach

For each price p:

buy1  = max(buy1,  -p)
sell1 = max(sell1, buy1 + p)
buy2  = max(buy2,  sell1 - p)
sell2 = max(sell2, buy2 + p)

Start buy1 = buy2 = -inf and sell1 = sell2 = 0. Return sell2. Since a second transaction of zero profit is always available, sell2 >= sell1 >= 0, so it already covers doing one or zero transactions.

Complexity

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

Edge Cases

• Single day → no transaction possible, 0
• Strictly decreasing prices → 0 (Example 3)
• Strictly increasing → one long transaction beats splitting it (Example 2)
• Two separate rises with a dip between → two transactions (Example 1)
• Price 0 is allowed; buy states can be exactly 0 and still valid
• -inf initial values must not be added to a price before being replaced; the max with -p on day one handles that

from typing import List


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        """
        123. Best Time to Buy and Sell Stock III
        Time: O(n)
        Space: O(1)
        """
        NEG = float("-inf")
        buy1 = buy2 = NEG   # cash while holding the 1st / 2nd share
        sell1 = sell2 = 0   # cash after selling the 1st / 2nd share

        for p in prices:
            buy1 = max(buy1, -p)
            sell1 = max(sell1, buy1 + p)
            buy2 = max(buy2, sell1 - p)
            sell2 = max(sell2, buy2 + p)

        return sell2

/**
 * 123. Best Time to Buy and Sell Stock III
 * Time: O(n)
 * Space: O(1)
 */
class Solution {
    public int maxProfit(int[] prices) {
        // cash while holding the 1st / 2nd share, and after selling each
        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;
    }
}