Best Time to Buy and Sell Stock III

Hard#123states

You get the price of one share for each day. Make at most two trades, each a buy and a later sell; you hold one share at a time, so the second buy comes after the first sale (the same day is fine). Find the largest total profit, or 0 if no trade pays. Our example: [2, 6, 3, 9, 4, 5] → 10, from 2 → 6 and 3 → 9.

123 Best Time to Buy and Sell Stock IIIWalkthrough · 1×

Example: prices [2, 6, 3, 9, 4, 5], at most two trades. Watch day 2: the second share is bought at 3 out of the profit of 2 → 6, and on day 3 that pair earns more than the single trade 2 → 9.

daystartprice021623394455buy1-2sell1buy2sell2
today, this stepbest money in this state after that daycomes from hereanswer and its trades

Before day 0, holding the 1st share means paying 2: buy1 = -2

01/41
restart · back · play · step
Speed
1function maxProfit(prices):
2 buy1 = -prices[0] // holding the 1st share
3 sell1 = 0 // the 1st trade is closed
4 buy2 = -prices[0] // holding the 2nd share
5 sell2 = 0 // the 2nd trade is closed
6 for d from 0 to len(prices) - 1:
7 p = prices[d]
8 buy1 = max(buy1, -p)
9 sell1 = max(sell1, buy1 + p)
10 buy2 = max(buy2, sell1 - p)
11 sell2 = max(sell2, buy2 + p)
12 return sell2
state
d
–
p
–
buy1
-2
sell1
–
buy2
–
sell2
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Four states cover every moment: holding the 1st share, after the 1st sale, holding the 2nd, after the 2nd sale. Each day a state either stays as it was or is entered from the state before it at today’s price, so its number is the best over every history that ends in it.
  2. buy2 = sell1 − p pays for the second share out of the first trade’s profit. That is how 2 → 6 and 3 → 9 (10) beat the single trade 2 → 9 (7): the dip from 6 to 3 is sold out of instead of sat through.
  3. The states are updated one after another on the same day, so a later one may read a value set today. That only adds a buy and a sell at the same price, which earn 0, so no profit is counted that is not there.

Complexity

Time O(n): one pass over the days, four updates on each. Memory O(1): four numbers, whatever the number of days.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.