Best Time to Buy and Sell Stock III
Four running balances: buy1, sell1, buy2, sell2 — at most two transactions
Track four numbers as you walk the prices once: the best cash balance after buying the first share, after selling it, after buying a second share (funded by the first sale's profit), and after selling that second share. Each balance can only improve today by either doing nothing or acting today at today's price, so every update is a max of 'keep yesterday' vs 'act now' — and sell2 at the end is the answer, since it is never better to leave a profitable second sale undone.
Details
Animated on: prices = [3,3,5,0,0,3,1,4] — at most two buy/sell transactions (never overlapping), maximize total profit.
Problem:Best Time to Buy and Sell Stock IIIHard
Four running balances: buy1, sell1, buy2, sell2 — at most two transactions
step 1 / 9
four running balances over prices [3, 3, 5, 0, 0, 3, 1, 4] — sell2 is the answer row
Day 0 (price=3): buy1 = -3 (the only way to own one share is to pay for it), sell1 = 0 (nothing sold yet), buy2 = -3 (spend the same cash to open the second position — there is no sell1 profit yet to fund it from), sell2 = 0 (no transaction closed).
1FUNCTION maxProfitIII(prices):2 buy1, buy2 <- -prices[0]3 sell1, sell2 <- 04 FOR i FROM 1 TO LENGTH(prices) - 1:5 buy1 <- MAX(buy1, -prices[i])6 sell1 <- MAX(sell1, buy1 + prices[i])7 buy2 <- MAX(buy2, sell1 - prices[i])8 sell2 <- MAX(sell2, buy2 + prices[i])9 RETURN sell2
← / → step · space play · Home restart
Every step in words
Show all 9 steps
- Day 0 (price=3): buy1 = -3 (the only way to own one share is to pay for it), sell1 = 0 (nothing sold yet), buy2 = -3 (spend the same cash to open the second position — there is no sell1 profit yet to fund it from), sell2 = 0 (no transaction closed).
- Day 1 (price=3): buy1 = max(-3, -3) = -3 — kept from before; sell1 = max(0, -3+3) = 0 — kept from before; buy2 = max(-3, 0-3) = -3 — kept from before; sell2 = max(0, -3+3) = 0 — no improvement today.
- Day 2 (price=5): buy1 = max(-3, -5) = -3 — kept from before; sell1 = max(0, -3+5) = 2 — better first sale; buy2 = max(-3, 2-5) = -3 — kept from before; sell2 = max(0, -3+5) = 2 — new best two-transaction profit.
- Day 3 (price=0): buy1 = max(-3, -0) = 0 — cheaper entry found; sell1 = max(2, 0+0) = 2 — kept from before; buy2 = max(-3, 2-0) = 2 — first sale's profit reinvested here; sell2 = max(2, 2+0) = 2 — no improvement today.
- Day 4 (price=0): buy1 = max(0, -0) = 0 — kept from before; sell1 = max(2, 0+0) = 2 — kept from before; buy2 = max(2, 2-0) = 2 — kept from before; sell2 = max(2, 2+0) = 2 — no improvement today.
- Day 5 (price=3): buy1 = max(0, -3) = 0 — kept from before; sell1 = max(2, 0+3) = 3 — better first sale; buy2 = max(2, 3-3) = 2 — kept from before; sell2 = max(2, 2+3) = 5 — new best two-transaction profit.
- Day 6 (price=1): buy1 = max(0, -1) = 0 — kept from before; sell1 = max(3, 0+1) = 3 — kept from before; buy2 = max(2, 3-1) = 2 — kept from before; sell2 = max(5, 2+1) = 5 — no improvement today.
- Day 7 (price=4): buy1 = max(0, -4) = 0 — kept from before; sell1 = max(3, 0+4) = 4 — better first sale; buy2 = max(2, 4-4) = 2 — kept from before; sell2 = max(5, 2+4) = 6 — new best two-transaction profit.
- sell2[7] = 6 is the answer: the best balance after closing at most two transactions, having walked every day exactly once.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.