Best Time to Buy and Sell Stock II - The Three Approaches

Problem: You are given an integer array prices where prices[i] is the price of a stock on day i. You can buy and sell the stock unlimited times, but you can only hold at most one share at a time. Return the maximum profit.

Example: prices = [7,1,5,3,6,4] → 7 (buy day 2 at 1, sell day 3 at 5 = profit 4; buy day 4 at 3, sell day 5 at 6 = profit 3; total = 7)

Example: prices = [1,2,3,4,5] → 4 (buy day 1 at 1, sell day 5 at 5 = profit 4)

---

Understanding the Problem

Key constraints:

• Can complete unlimited transactions
• Can only hold at most one share at a time
• Must sell before buying again

Key insight: This is a state machine problem where you're in one of two states at any time:

• Holding a stock
• Not holding a stock

---

1. Pure Recursion (Unoptimized - O(2^n))

The Intuition

Key Insight: At each day, we have different choices based on our current state:

• If holding: can sell or do nothing
• If not holding: can buy or do nothing

Recursive Logic:

maxProfit(day, holding):
    if day >= n: return 0

    if holding:
        // Option 1: Sell today
        sell = prices[day] + maxProfit(day+1, false)
        // Option 2: Do nothing (keep holding)
        hold = maxProfit(day+1, true)
        return max(sell, hold)
    else:
        // Option 1: Buy today
        buy = -prices[day] + maxProfit(day+1, true)
        // Option 2: Do nothing (stay not holding)
        skip = maxProfit(day+1, false)
        return max(buy, skip)

public int maxProfit(int[] prices) {
    return helper(prices, 0, false);  // start day 0, not holding
}

private int helper(int[] prices, int day, boolean holding) {
    // Base case: no more days
    if (day >= prices.length) {
        return 0;
    }

    if (holding) {
        // Currently holding stock
        // Option 1: Sell today
        int sell = prices[day] + helper(prices, day + 1, false);
        // Option 2: Do nothing (keep holding)
        int hold = helper(prices, day + 1, true);
        return Math.max(sell, hold);
    } else {
        // Not holding stock
        // Option 1: Buy today
        int buy = -prices[day] + helper(prices, day + 1, true);
        // Option 2: Do nothing (stay not holding)
        int skip = helper(prices, day + 1, false);
        return Math.max(buy, skip);
    }
}

What Happens with prices = [7,1,5,3,6,4]:

helper(0, false): day 0, not holding
  buy: -7 + helper(1, true)
       helper(1, true): holding
         sell: 1 + helper(2, false)
         hold: helper(2, true)
  skip: helper(1, false)
        helper(1, false): not holding
          buy: -1 + helper(2, true)
          skip: helper(2, false)

This branches exponentially...

Optimal path:
Day 0 (price=7): skip (not holding)
Day 1 (price=1): buy (now holding) → profit = -1
Day 2 (price=5): sell (not holding) → profit = -1 + 5 = 4
Day 3 (price=3): buy (holding) → profit = 4 - 3 = 1
Day 4 (price=6): sell (not holding) → profit = 1 + 6 = 7
Day 5 (price=4): skip (not holding) → profit = 7

Result: 7

Call Tree Visualization:

helper(0, false)
├── buy: -7 + helper(1, true)
│   ├── sell: 1 + helper(2, false) ✓ COMPUTED
│   └── hold: helper(2, true) ✓ COMPUTED
└── skip: helper(1, false)
    ├── buy: -1 + helper(2, true) ✓ DUPLICATE!
    └── skip: helper(2, false) ✓ DUPLICATE!

Problem: helper(2, false) and helper(2, true) computed multiple times!

Why is it Slow?

Overlapping subproblems: States like (day=2, holding=false) are computed many times.

For n days, there are 2n possible states (day, holding), but pure recursion explores them exponentially.

Complexity:

• Time: O(2^n) - each day branches into 2 choices
• Space: O(n) - recursion stack depth

---

2. Top-Down DP (Memoization - O(n))

The Intuition

Key Insight: Same recursive logic, but cache results for each (day, holding) state.

public int maxProfit(int[] prices) {
    int n = prices.length;
    // memo[day][holding] where holding: 0 = false, 1 = true
    Integer[][] memo = new Integer[n][2];
    return helper(prices, 0, 0, memo);  // start day 0, not holding (0)
}

private int helper(int[] prices, int day, int holding, Integer[][] memo) {
    // Base case
    if (day >= prices.length) {
        return 0;
    }

    // Check cache
    if (memo[day][holding] != null) {
        return memo[day][holding];
    }

    int result;
    if (holding == 1) {
        // Currently holding stock
        int sell = prices[day] + helper(prices, day + 1, 0, memo);
        int hold = helper(prices, day + 1, 1, memo);
        result = Math.max(sell, hold);
    } else {
        // Not holding stock
        int buy = -prices[day] + helper(prices, day + 1, 1, memo);
        int skip = helper(prices, day + 1, 0, memo);
        result = Math.max(buy, skip);
    }

    // Store in cache
    memo[day][holding] = result;
    return result;
}

What Happens with prices = [7,1,5,3,6,4]:

Call helper(0, 0, memo):
  memo[0][0] is null, calculate:
  buy = -7 + helper(1, 1, memo)
        helper(1, 1, memo):
          memo[1][1] is null, calculate:
          sell = 1 + helper(2, 0, memo)
                 helper(2, 0, memo):
                   ... (continues)
                 → memo[2][0] = 4
          hold = helper(2, 1, memo)
                 → memo[2][1] = 5
          → max(1+4, 5) = 5
          → memo[1][1] = 5
  skip = helper(1, 0, memo)
         memo[1][0] is null, calculate:
         buy = -1 + helper(2, 1, memo) → -1 + 5 = 4
         skip = helper(2, 0, memo) → 4 (already cached!)
         → max(4, 4) = 4
         → memo[1][0] = 4
  → max(-7+5, 4) = max(-2, 4) = 4

Wait, that's wrong. Let me recalculate...

Actually, let's trace backwards from the end:

memo[5][0] = 0 (base case: no more days)
memo[5][1] = 0 (base case)

memo[4][0]: not holding on day 4
  buy = -4 + memo[5][1] = -4 + 0 = -4
  skip = memo[5][0] = 0
  → max(-4, 0) = 0
  memo[4][0] = 0

memo[4][1]: holding on day 4
  sell = 4 + memo[5][0] = 4 + 0 = 4
  hold = memo[5][1] = 0
  → max(4, 0) = 4
  memo[4][1] = 4

memo[3][0]: not holding on day 3
  buy = -3 + memo[4][1] = -3 + 4 = 1
  skip = memo[4][0] = 0
  → max(1, 0) = 1
  memo[3][0] = 1

memo[3][1]: holding on day 3
  sell = 3 + memo[4][0] = 3 + 0 = 3
  hold = memo[4][1] = 4
  → max(3, 4) = 4
  memo[3][1] = 4

... (continue backwards)

Final: memo[0][0] = 7

Memoization Table:

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

memo[day][holding]:
            not_holding(0)  holding(1)
day 0            7              2
day 1            7              5
day 2            7              5
day 3            7              4
day 4            4              4
day 5            0              0

Each state computed exactly once!

Execution Order:

Bottom-up filling (conceptually):
1. memo[5][0] = 0, memo[5][1] = 0
2. memo[4][0] = 0, memo[4][1] = 4
3. memo[3][0] = 1, memo[3][1] = 4
4. memo[2][0] = 7, memo[2][1] = 5
5. memo[1][0] = 7, memo[1][1] = 5
6. memo[0][0] = 7, memo[0][1] = 2

Total computations: 2n = O(n)

Complexity:

• Time: O(n) - 2n states, each computed once
• Space: O(n) - memo table + O(n) recursion stack

---

3. Bottom-Up DP (Tabulation - O(n))

The Intuition

Key Insight: Build solutions from day 0 to day n-1 systematically.

State: dp[i][holding] = max profit on day i when in state holding

• dp[i][0] = max profit on day i when not holding
• dp[i][1] = max profit on day i when holding

Transition:

// Not holding on day i:
dp[i][0] = max(
    dp[i-1][0],              // already not holding (skip)
    dp[i-1][1] + prices[i]   // sell today
)

// Holding on day i:
dp[i][1] = max(
    dp[i-1][1],              // already holding (hold)
    dp[i-1][0] - prices[i]   // buy today
)

public int maxProfit(int[] prices) {
    int n = prices.length;
    int[][] dp = new int[n][2];
    // dp[i][0] = not holding, dp[i][1] = holding

    // Base case: day 0
    dp[0][0] = 0;           // not holding: no profit
    dp[0][1] = -prices[0];  // holding: paid for stock

    for (int i = 1; i < n; i++) {
        // Not holding: either already not holding, or sell today
        dp[i][0] = Math.max(
            dp[i-1][0],              // skip (already not holding)
            dp[i-1][1] + prices[i]   // sell today
        );

        // Holding: either already holding, or buy today
        dp[i][1] = Math.max(
            dp[i-1][1],              // hold (already holding)
            dp[i-1][0] - prices[i]   // buy today
        );
    }

    return dp[n-1][0];  // must end not holding
}

What Happens with prices = [7,1,5,3,6,4]:

Day 0: price = 7
dp[0][0] = 0        // not holding
dp[0][1] = -7       // buy at 7

Day 1: price = 1
dp[1][0] = max(dp[0][0], dp[0][1] + 1)
         = max(0, -7 + 1) = max(0, -6) = 0
dp[1][1] = max(dp[0][1], dp[0][0] - 1)
         = max(-7, 0 - 1) = max(-7, -1) = -1

Day 2: price = 5
dp[2][0] = max(dp[1][0], dp[1][1] + 5)
         = max(0, -1 + 5) = max(0, 4) = 4
dp[2][1] = max(dp[1][1], dp[1][0] - 5)
         = max(-1, 0 - 5) = max(-1, -5) = -1

Day 3: price = 3
dp[3][0] = max(dp[2][0], dp[2][1] + 3)
         = max(4, -1 + 3) = max(4, 2) = 4
dp[3][1] = max(dp[2][1], dp[2][0] - 3)
         = max(-1, 4 - 3) = max(-1, 1) = 1

Day 4: price = 6
dp[4][0] = max(dp[3][0], dp[3][1] + 6)
         = max(4, 1 + 6) = max(4, 7) = 7
dp[4][1] = max(dp[3][1], dp[3][0] - 6)
         = max(1, 4 - 6) = max(1, -2) = 1

Day 5: price = 4
dp[5][0] = max(dp[4][0], dp[4][1] + 4)
         = max(7, 1 + 4) = max(7, 5) = 7
dp[5][1] = max(dp[4][1], dp[4][0] - 4)
         = max(1, 7 - 4) = max(1, 3) = 3

Result: dp[5][0] = 7 ✓

DP Table Evolution:

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

Day 0:
       not_holding(0)  holding(1)
day 0       0             -7

Day 1:
       not_holding(0)  holding(1)
day 0       0             -7
day 1       0             -1

Day 2:
       not_holding(0)  holding(1)
day 0       0             -7
day 1       0             -1
day 2       4             -1

Day 3:
       not_holding(0)  holding(1)
day 0       0             -7
day 1       0             -1
day 2       4             -1
day 3       4              1

Day 4:
       not_holding(0)  holding(1)
day 0       0             -7
day 1       0             -1
day 2       4             -1
day 3       4              1
day 4       7              1

Day 5:
       not_holding(0)  holding(1)
day 0       0             -7
day 1       0             -1
day 2       4             -1
day 3       4              1
day 4       7              1
day 5       7              3  ← Answer: 7

Step-by-step with prices = [1,2,3,4,5]:

Day 0: price = 1
dp[0][0] = 0
dp[0][1] = -1

Day 1: price = 2
dp[1][0] = max(0, -1+2) = 1
dp[1][1] = max(-1, 0-2) = -1

Day 2: price = 3
dp[2][0] = max(1, -1+3) = 2
dp[2][1] = max(-1, 1-3) = -1

Day 3: price = 4
dp[3][0] = max(2, -1+4) = 3
dp[3][1] = max(-1, 2-4) = -1

Day 4: price = 5
dp[4][0] = max(3, -1+5) = 4
dp[4][1] = max(-1, 3-5) = -1

Result: 4 ✓ (buy at 1, sell at 5)

Complexity:

• Time: O(n) - single pass through days
• Space: O(n) - dp table (can be optimized to O(1))

---

Space Optimization: O(1)

Since we only need the previous day's values, we can optimize to O(1) space:

public int maxProfit(int[] prices) {
    int notHolding = 0;
    int holding = -prices[0];

    for (int i = 1; i < prices.length; i++) {
        int newNotHolding = Math.max(notHolding, holding + prices[i]);
        int newHolding = Math.max(holding, notHolding - prices[i]);

        notHolding = newNotHolding;
        holding = newHolding;
    }

    return notHolding;
}

---

Quick Comparison

Feature	Pure Recursion	Memoization	Tabulation	Space Optimized
Structure	Recursive	Recursive + cache	Loop + array	Loop + variables
Direction	Top-down	Top-down	Bottom-up	Bottom-up
Time	O(2^n)	O(n)	O(n)	O(n)
Space	O(n) stack	O(n) memo + stack	O(n) array	O(1)
Intuition	"Try all choices"	"Cache recursive results"	"Build day by day"	"Only track prev day"
When to use	Never (too slow)	Learning recursion	Clear state machine	Production code

---

The Evolution

Approach 1 → Approach 2:

// Add memoization
if (memo[day][holding] != null) return memo[day][holding];

int result = ... // compute
memo[day][holding] = result;
return result;

Approach 2 → Approach 3:

// Replace recursion with loop
for (int i = 1; i < n; i++) {
    dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
    dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);
}

Approach 3 → Space Optimized:

// Use variables instead of array
int notHolding = 0, holding = -prices[0];
for each day:
    update notHolding and holding using previous values

---

Mental Models

Pure Recursion: "At each day, explore all possible actions: buy, sell, hold, skip. This creates a tree of all possibilities."

Memoization: "Same exploration, but remember what I've already computed for each (day, state) pair."

Tabulation: "Systematically build profit for each day and state, using the previous day's results."

Space Optimized: "I only need yesterday's values to compute today's. No need to remember all history."

---

State Machine Visualization

┌──────────────────┐                  ┌──────────────────┐
│   Not Holding    │                  │     Holding      │
│   (profit: p)    │ ──────────────→  │  (profit: p-c)   │
│                  │  buy (cost: c)   │                  │
└──────────────────┘                  └──────────────────┘
        ↑                                      │
        │                                      │
        └──────────────────────────────────────┘
               sell (gain: price)

States: 2 (holding, not_holding)
Transitions:
  - not_holding → holding (buy: -price)
  - holding → not_holding (sell: +price)
  - holding → holding (hold)
  - not_holding → not_holding (skip)

---

Which Approach to Use?

Use Pure Recursion when:

• ❌ Never in production - too slow (O(2^n))
• ✅ Only for initial understanding
• ✅ Helps visualize the decision tree

Use Memoization when:

• ✅ You want to think recursively
• ✅ Learning the state machine concept
• ✅ Converting recursive solution to DP

Use Tabulation when:

• ✅ You want clear state transitions
• ✅ Learning interval DP patterns
• ✅ Need to see the full DP table

Use Space Optimized when:

• ✅ Production code - fastest and most efficient
• ✅ You understand the pattern and want optimal solution
• ✅ Space is a concern

---

Complete Working Example

public class BestTimeToBuySellStockII {

    // Approach 1: Pure Recursion (SLOW - for understanding only)
    public int maxProfitRecursive(int[] prices) {
        return helperRecursive(prices, 0, false);
    }

    private int helperRecursive(int[] prices, int day, boolean holding) {
        if (day >= prices.length) return 0;

        if (holding) {
            int sell = prices[day] + helperRecursive(prices, day + 1, false);
            int hold = helperRecursive(prices, day + 1, true);
            return Math.max(sell, hold);
        } else {
            int buy = -prices[day] + helperRecursive(prices, day + 1, true);
            int skip = helperRecursive(prices, day + 1, false);
            return Math.max(buy, skip);
        }
    }

    // Approach 2: Memoization
    public int maxProfitMemo(int[] prices) {
        int n = prices.length;
        Integer[][] memo = new Integer[n][2];
        return helperMemo(prices, 0, 0, memo);
    }

    private int helperMemo(int[] prices, int day, int holding, Integer[][] memo) {
        if (day >= prices.length) return 0;
        if (memo[day][holding] != null) return memo[day][holding];

        int result;
        if (holding == 1) {
            int sell = prices[day] + helperMemo(prices, day + 1, 0, memo);
            int hold = helperMemo(prices, day + 1, 1, memo);
            result = Math.max(sell, hold);
        } else {
            int buy = -prices[day] + helperMemo(prices, day + 1, 1, memo);
            int skip = helperMemo(prices, day + 1, 0, memo);
            result = Math.max(buy, skip);
        }

        memo[day][holding] = result;
        return result;
    }

    // Approach 3: Tabulation
    public int maxProfitDP(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];

        dp[0][0] = 0;
        dp[0][1] = -prices[0];

        for (int i = 1; i < n; i++) {
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
        }

        return dp[n-1][0];
    }

    // Approach 4: Space Optimized
    public int maxProfitOptimized(int[] prices) {
        int notHolding = 0;
        int holding = -prices[0];

        for (int i = 1; i < prices.length; i++) {
            int newNotHolding = Math.max(notHolding, holding + prices[i]);
            int newHolding = Math.max(holding, notHolding - prices[i]);
            notHolding = newNotHolding;
            holding = newHolding;
        }

        return notHolding;
    }

    public static void main(String[] args) {
        BestTimeToBuySellStockII solution = new BestTimeToBuySellStockII();
        int[] prices1 = {7, 1, 5, 3, 6, 4};
        int[] prices2 = {1, 2, 3, 4, 5};

        System.out.println("Test 1: [7,1,5,3,6,4]");
        System.out.println("Pure Recursion: " + solution.maxProfitRecursive(prices1)); // 7
        System.out.println("Memoization: " + solution.maxProfitMemo(prices1));           // 7
        System.out.println("Tabulation: " + solution.maxProfitDP(prices1));              // 7
        System.out.println("Space Optimized: " + solution.maxProfitOptimized(prices1));  // 7

        System.out.println("\nTest 2: [1,2,3,4,5]");
        System.out.println("Pure Recursion: " + solution.maxProfitRecursive(prices2)); // 4
        System.out.println("Memoization: " + solution.maxProfitMemo(prices2));           // 4
        System.out.println("Tabulation: " + solution.maxProfitDP(prices2));              // 4
        System.out.println("Space Optimized: " + solution.maxProfitOptimized(prices2));  // 4
    }
}

---

Common Pitfalls

Pitfall 1: Wrong base case initialization

// WRONG - holding on day 0 should be negative
dp[0][1] = 0;

// RIGHT - holding means we bought the stock
dp[0][1] = -prices[0];

Pitfall 2: Forgetting to use previous state

// WRONG - can't buy if already holding
dp[i][1] = -prices[i];

// RIGHT - buy from "not holding" state
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);

Pitfall 3: Wrong return value

// WRONG - might be holding stock at end
return max(dp[n-1][0], dp[n-1][1]);

// RIGHT - must end not holding (sold everything)
return dp[n-1][0];

Pitfall 4: Space optimization variable update order

// WRONG - overwrites value before using it
notHolding = Math.max(notHolding, holding + prices[i]);
holding = Math.max(holding, notHolding - prices[i]);  // uses NEW notHolding!

// RIGHT - save to temp variables first
int newNotHolding = Math.max(notHolding, holding + prices[i]);
int newHolding = Math.max(holding, notHolding - prices[i]);
notHolding = newNotHolding;
holding = newHolding;

---

Practice Extensions

Once you master these approaches, try:

1. Best Time to Buy and Sell Stock I (LC 121): Only one transaction
2. Best Time to Buy and Sell Stock III (LC 123): At most two transactions
3. Best Time to Buy and Sell Stock IV (LC 188): At most k transactions
4. Best Time to Buy and Sell Stock with Cooldown (LC 309): 1-day cooldown after selling
5. Best Time to Buy and Sell Stock with Transaction Fee (LC 714): Fee on each transaction

---

Key Takeaways

THE STATE MACHINE FOUNDATION

Pure Recursion: Explore all possible decision trees

• Think: "Try all actions at each day"
• Use: Only for understanding

Memoization: Cache results to avoid recomputation

• Think: "Remember what I've already solved"
• Use: Learning state machines

Tabulation: Build systematically from base cases

• Think: "Build day by day using previous results"
• Use: Clear visualization of states

Space Optimized: Use only what you need

• Think: "Yesterday's values → today's values"
• Use: Production code

Key insight: At each day, you're in a state (holding or not). From each state, you can transition to other states with specific costs/gains.

---

The Big Picture

Best Time to Buy and Sell Stock II is the foundation of state machine DP.

Master it, and you'll understand:

• How to model problems as state machines
• State transitions with costs/gains
• Progressive optimization from O(2^n) → O(n) time and O(n) → O(1) space
• Multiple approaches to the same problem

This is your state machine foundation. Build it strong.