AlgoViz
HomeDynamic Programming

Best time to buy and sell stock II

Medium

Collect every upward move

Problem

Maximize profit with as many buy/sell transactions as you like (one at a time).

In simple words

Since you can trade freely, pocket every upward step between consecutive days.

The idea

With unlimited transactions the total profit is the sum of every positive day-to-day increase, since any longer rise decomposes into those steps. No state machine is needed.

The trick

  • Add max(0, price[i] - price[i-1]) each day.
  • Equivalent to the two-state hold/free DP, but far simpler.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

7
1
5
3
6
4
0
1
2
3
4
5

Step 1 of 2. Here's the example — [7,1,5,3,6,4] Values: 7, 1, 5, 3, 6, 4.

1/2
Optimal
timeO(n)spaceO(1)
1profit=02for i in 1..n-1: if p[i]>p[i-1]: profit+=p[i]-p[i-1]3return profit

Input

array
[7, 1, 5, 3, 6, 4]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
prices = [7, 1, 5, 3, 6, 4]
Output:
7
Explanation:
Grab every rise: (5-1)+(6-3) = 7.

Example 2

Input:
prices = [1, 2, 3, 4, 5]
Output:
4
Explanation:
One long climb → profit 4.

Example 3

Input:
prices = [7, 6, 4, 3, 1]
Output:
0
Explanation:
Only falls → 0 profit.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.