3.15 Best Time to Buy and Sell Stock II

3.15.1 Problem Metadata

3.15.2 Description

You may complete as many stock transactions as you like (buy before sell, no overlapping transactions). Return the maximum profit.

3.15.3 Examples

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy at 1, sell at 5; buy at 3, sell at 6.

3.15.4 Constraints

  • 1 <= prices.length <= 10^5

3.15.5 Solution - Sum Positive Differences

3.15.5.1 Walkthrough

This solution uses a greedy approach to maximize profit by capturing every upward price movement.

Core Strategy:

Unlike Stock I (single transaction), here we can make unlimited transactions. The key insight is: - Capture every price increase as profit - Ignore every price decrease (don’t trade)

This greedy strategy works because: - Any continuous upward trend a → b → c yields the same profit whether we: 1. Buy at a, sell at c (one transaction): profit = c - a 2. Buy at a, sell at b, buy at b, sell at c (two transactions): profit = (b - a) + (c - b) = c - a - Multiple small transactions equal one large transaction across the same range

Key Insight: Why This Greedy Choice is Optimal

At each day, we make a simple greedy choice: - If price increased today: Capture the profit (buy yesterday, sell today) - If price decreased today: Do nothing

This locally optimal choice (capture every increase) leads to the globally optimal solution because: - We never miss profitable opportunities - We never take losing trades - The sum of all positive differences equals the maximum possible profit

Visual Example Walkthrough:

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

Day 0→1: 7→1 (decrease by 6)
  No profit captured (skip this day)
  profit = 0

Day 1→2: 1→5 (increase by 4) ✓
  Greedy choice: BUY at 1, SELL at 5
  profit += (5 - 1) = 4
  profit = 4

Day 2→3: 5→3 (decrease by 2)
  No profit captured (skip this day)
  profit = 4

Day 3→4: 3→6 (increase by 3) ✓
  Greedy choice: BUY at 3, SELL at 6
  profit += (6 - 3) = 3
  profit = 7

Day 4→5: 6→4 (decrease by 2)
  No profit captured (skip this day)
  profit = 7

Result: 7 (transactions: buy@1 sell@5, buy@3 sell@6)

Alternative Interpretation:

You can think of this as “riding every uphill” on the price chart:

     5        6
    /        /
   /   3    /
  /   /    /
 /   /    /
7   /    /  4
   1

We ride up from 1→5 (profit=4) and 3→6 (profit=3), total=7.

Why This Greedy Strategy Works:

  • Greedy property: Capturing each individual price increase is always optimal
  • No need to look ahead: Each local decision (capture increase or not) is independent
  • Proof: Sum of positive differences = maximum profit achievable with unlimited transactions
  • This guarantees we extract all possible profit from the price sequence

3.15.5.2 Analysis

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

3.15.5.3 Implementation Steps

  1. Initialize profit = 0.
  2. For each day i > 0, if prices[i] > prices[i-1], add the difference to profit.
  3. Return profit.

3.15.5.4 Code - Java

public int maxProfit(int[] prices) {
    int profit = 0;
    for (int i = 1; i < prices.length; i++) {
        if (prices[i] > prices[i - 1]) {
            profit += prices[i] - prices[i - 1];
        }
    }
    return profit;
}