Best Time to Buy and Sell Stock III

Best Time to Buy and Sell Stock III raises the stakes: instead of one trade, you may do at most two. The clever part is that you do not need a 2-D table — four running variables sweep the prices once and give the answer.

The slow way first

The brute force is to pick a day to split the timeline, run the single-transaction solution on the left half and on the right half, and add the two best profits. Trying every split point is O(n²) (and naive pair-checking inside each half is even worse). For a long price history that is far too slow.

The question to ask: can I carry the best result of each stage forward as I walk the array, instead of recomputing? Yes — and it collapses to four numbers.

The idea: four running balances

Think of your balance (cash on hand) after each action, where buying subtracts the price and selling adds it. Track the best possible balance after each of the four stages:

• buy1 — best balance after the first buy (we spent p, so it is -p or better).
• sell1 — best balance after the first sell (buy1 + p).
• buy2 — best balance after the second buy, paid for out of the first profit (sell1 - p).
• sell2 — best balance after the second sell (buy2 + p). This is the answer.

Each day, we update all four with the current price p. Because buy2 is built from sell1, and sell2 from buy2, the second transaction automatically reuses the profit of the first. Updating them top-to-bottom on the same price is fine: it just means "I could also buy and sell again today," which never hurts.

Walk through it

Step through the animation. The pointer p scans the prices left to right; the four labels show each best balance updating. Watch sell2 climb: it only ever goes up, and by the last day it holds the maximum two-transaction profit, 6.

Pseudocode

buy1, buy2 = -infinity, -infinity      # best balance after each buy
sell1, sell2 = 0, 0                     # best balance after each sell
for each price p in prices:
    buy1  = max(buy1,  -p)              # spend p on the first buy
    sell1 = max(sell1, buy1 + p)        # recover p on the first sell
    buy2  = max(buy2,  sell1 - p)       # spend p again, funded by sell1
    sell2 = max(sell2, buy2 + p)        # recover p on the second sell
return sell2                            # most money after <= 2 trades

The Python solution

def max_profit(prices):
    buy1 = buy2 = float('-inf')
    sell1 = sell2 = 0
    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

• buy1/buy2 start at negative infinity so the very first price forces a real buy.
• sell1/sell2 start at 0: doing no trade yields zero profit.
• Line 5: buy1 is the best balance if we are currently holding the first stock — pay p now, or keep an earlier (cheaper) buy.
• Line 6: sell1 adds p to the best first buy — the best profit from one completed trade.
• Line 7: buy2 spends p again but starts from sell1, so the second purchase is funded by the first profit.
• Line 8: sell2 is the final answer — the best balance after both trades complete.

Complexity

We replaced a 2-D DP table with four scalars, so the space is O(1). The same trick generalizes: for k transactions you keep 2k running balances.

When this pattern shows up

Practice