Best Time to Buy and Sell Stock II

You may complete as many transactions as you like (buy then sell), but you cannot hold more than one share at a time. Return the maximum total profit.

A full DP works, but a simple greedy scan is optimal: sum every upward price step.

Why this is worth learning

Without fees, cooldowns, or a transaction limit, the value of holding across several days telescopes into adjacent price changes. Only positive changes need to be collected.

Before coding: one-minute experiment

For [1,4,2,5], compare the best one-trade profit with unlimited-trade profit.

Function signature

func MaxProfitII(prices []int) int

Inputs / outputs

• prices: prices[i] is the price on day i.
• Return: the maximum profit with unlimited transactions.

Example

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

Profit = (5-1) + (6-3).

Constraints

• 1 <= len(prices) <= 100_000
• 0 <= prices[i] <= 1_000_000_000
• The full domain uses the course's 64-bit Go target: accumulated profit can reach 50_000 × 1_000_000_000 = 5 × 10^13.

Core idea (near-solution)

Any increasing segment a < b < c yields profit (c-a), which equals (b-a) + (c-b). So you can capture the same profit by summing every positive day-to-day gain.

Invariant: after day i, profit equals the maximum achievable profit using prices up to i with unlimited transactions.

Algorithm (step-by-step)

1. Initialize profit = 0.
2. For each i from 1 to len(prices)-1:
   • If prices[i] > prices[i-1], add prices[i] - prices[i-1] to profit.
3. Return profit.

Correctness sketch

For any purchase on day a and sale on day b, the profit equals the sum of consecutive differences from a+1 through b. Keeping only positive differences gives an upper bound on that trade, and therefore on any set of non-overlapping trades. This upper bound is attainable by buying at the start and selling at the end of each increasing run. Summing positive adjacent differences thus achieves the maximum, not merely a local improvement. The argument stops applying as soon as fees, cooldowns, or transaction limits couple decisions across runs.

Trace (hand walkthrough)

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

Profit = (5-1) + (6-3).

Walk:
- diffs: 1-7=-6 (skip)
- 5-1=4 (take) -> profit=4
- 3-5=-2 (skip)
- 6-3=3 (take) -> profit=7
- 4-6=-2 (skip) -> final profit=7

Pitfalls to avoid

• Adding negative changes, which charges for declines you can avoid.
• Applying this independent-rise rule after introducing fees, cooldowns, or transaction limits. A DP is valid, but must encode those extra constraints explicitly.

Debugging lens

Alternating low and high prices distinguish this task from the single-trade version. Accumulated profit may exceed 32-bit range under the published bounds; the supplied runner is a 64-bit environment.

Complexity

• Time: O(n)
• Extra space: O(1)

Implementation notes (Go)

• Use a running integer sum.

Reconstruction checkpoint

For [1,4,2,5], compare the best one-trade profit with unlimited-trade profit.

Return to Array & String · Module quiz