Pattern visualizer
Best Time to Buy and Sell Stock III
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. Animated on: prices = [3,3,5,0,0,3,1,4] — at most two buy/sell transactions (never overlapping), maximize total profit..
Four running balances: buy1, sell1, buy2, sell2 — at most two transactions
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