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.

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

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

• Invariant: after day i, profit equals the maximum achievable profit using prices up to i with unlimited transactions.
• The algorithm maintains a feasible best-so-far state while scanning.
• Each greedy update preserves feasibility and never discards a possible optimal answer.
• When the scan ends, the recorded state represents the optimal solution.

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

• Overcomplicating with DP when greedy is enough.
• Attempting to buy and sell on the same day (profit is zero).

Complexity

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

Implementation notes (Go)

• Use a running integer sum.