Best Time to Buy and Sell Stock III
Max profit using at most two non-overlapping buy-sell transactions.
Open on LeetCode ↗Intuition
The obvious-looking shortcut is to find the two best individual gains anywhere in the array, say the biggest rise on the left half and the biggest rise on the right half, and add them. Those two windows can OVERLAP in time, which is illegal: the second buy has to happen strictly after the first sell closes out. Instead track four running states, buy1, sell1, buy2, sell2, where each is built only from the state immediately before it in the chain. buy2 can only spend money that sell1 already banked, so the ordering constraint is enforced by construction rather than by checking indices afterward.
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.
Approach
Four states, one dependency chain
buy1 = best cash position after one purchase, sell1 = best profit after closing that one trade, buy2 = best cash position after a second purchase funded out of sell1's profit, sell2 = best profit after closing a second trade. Initialize buy1 = buy2 = -prices[0], sell1 = sell2 = 0.
Update in dependency order each day
For each day's price: buy1 = max(buy1, -price); sell1 = max(sell1, buy1 + price); buy2 = max(buy2, sell1 - price); sell2 = max(sell2, buy2 + price). Because buy2 reads sell1 and sell2 reads buy2, using the SAME day's already-updated sell1/buy2 is fine here since a buy and sell can't happen on the same day profitably in a way that breaks this, and it keeps the whole thing to one pass.
Answer is sell2
sell2 is a running max seeded from sell1's history, so if a second trade never helps, sell2 simply never rises above sell1 and the recurrence naturally falls back to using only one transaction (or zero).
Solution & live demo
Common pitfalls
Splitting the array at every index
for i in range(n):
best = max(best, maxOne(prices[:i]) + maxOne(prices[i:]))buy2 = max(buy2, sell1 - prices[i])
That's O(n²), or O(n) with two precomputed arrays. The four chained states carry the same information in four scalars and one pass.
Updating the states in reverse order
sell2 = max(sell2, buy2 + prices[i]) buy2 = max(buy2, sell1 - prices[i]) ...
buy1 = ...; sell1 = ...; buy2 = ...; sell2 = ...
Each state depends on the one before it on the same day — that's what allows buying and selling on the same index, which is a legal no-op. Reversing the order breaks the chain and undercounts.
Initialising buy2 to zero
buy2 = 0
buy2 = -prices[0]
buy2 holds profit-minus-cost after two purchases, which starts negative. Seeding at 0 pretends a share was acquired for free and inflates the answer.
Edge cases
buy1, buy2 chase the lowest price but sell1, sell2 never exceed 0, so the answer correctly stays 0 with no forced losing trade.
sell2 stays equal to sell1 throughout since a second trade never improves on it, correctly reducing to the single-transaction answer.
With 0 or 1 prices there is no valid transaction; the loop from day 1 onward simply does not run and profit stays 0.
buy2 only ever draws funds from sell1, which already reflects a closed first trade, so the two captured gains cannot overlap in time.