Best Time to Buy and Sell Stock II

Medium#122every rise

You get the price of a share for each day. You may buy and sell as many times as you like, but hold at most one share at a time; selling and buying again on the same day is allowed. Find the largest total profit. Our example: [5, 2, 4, 7, 6, 3, 8] — the answer is 10: buy at 2 and sell at 7, then buy at 3 and sell at 8.

122 Best Time to Buy and Sell Stock IIWalkthrough · 1×

Example: [5, 2, 4, 7, 6, 3, 8], a bar per day. Each rise from one day to the next is added to profit; its part of the bar is marked.

50214273643586profit0
day not reachedday i − 1day irise taken into profitpassed

Nothing earned yet: profit = 0

01/23
restart · back · play · step
Speed
1function maxProfit(prices):
2 profit = 0
3 for i from 1 to len(prices) - 1:
4 rise = prices[i] - prices[i - 1]
5 if rise > 0:
6 profit = profit + rise
7 return profit
state
profit
0
i
–
rise
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Any trade from day a to day b earns prices[b] − prices[a], which is the sum of the day-to-day changes in between. So one long trade over a climb earns exactly what its rises add up to.
  2. A trade that spans a drop pays for that drop. Leaving out every negative change and keeping every positive one is the largest sum the changes can give.
  3. Each rise is one trade of one day, and those never overlap, so this sum can really be earned with one share at a time.

Complexity

Time O(n): one pass over the days. Memory O(1): only profit and the current rise.

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.