Best Time to Buy and Sell Stock II

The key idea

Every upward step prices[i] > prices[i-1] can be captured as its own buy-yesterday/sell-today trade, because you may transact as many times as you like. Summing all those positive day-to-day differences equals the maximum profit, since any longer winning run is just the sum of its consecutive up-steps.

Problem

You are given an integer array prices where prices[i] is the price of a given stock on the i-th day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Constraints

1 <= prices.length <= 3 * 10^4
0 <= prices[i] <= 10^4

Examples

Input: prices = [7,1,5,3,6,4] Output: 7

Input: prices = [1,2,3,4,5] Output: 4

Input: prices = [7,6,4,3,1] Output: 0

Complexity

Time: O(n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →