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

Problem: You are given an array prices where prices[i] is the price of a stock on day i. Find the maximum profit you can achieve. You may complete at most two transactions. Note: You cannot engage in multiple transactions simultaneously (must sell before buying again).

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

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

---

Understanding the Problem

Key constraints:

• Can complete at most 2 transactions
• Must sell before buying again (no simultaneous holdings)
• Each transaction = 1 buy + 1 sell

Key insight: This is a 3D state machine problem with three dimensions:

• Day (position in array)
• Transactions remaining (0, 1, or 2)
• Holding status (holding or not holding)

---

1. Pure Recursion (Unoptimized - Exponential)

The Intuition

Key Insight: At each day, our choices depend on:

• How many transactions we have left
• Whether we're currently holding stock

Recursive Logic:

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

    if holding:
        // Option 1: Sell today (completes a transaction)
        sell = prices[day] + maxProfit(day+1, transactions_left-1, false)
        // Option 2: Keep holding
        hold = maxProfit(day+1, transactions_left, true)
        return max(sell, hold)
    else:
        // Option 1: Buy today (starts a transaction)
        buy = -prices[day] + maxProfit(day+1, transactions_left, true)
        // Option 2: Do nothing
        skip = maxProfit(day+1, transactions_left, false)
        return max(buy, skip)

Important: We decrement transactions_left when we sell (complete the transaction), not when we buy.

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

private int helper(int[] prices, int day, int transactionsLeft, boolean holding) {
    // Base cases
    if (day >= prices.length) return 0;
    if (transactionsLeft == 0) return 0;

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

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

helper(0, 2, false): day 0, 2 transactions left, not holding
  buy: -3 + helper(1, 2, true)
  skip: helper(1, 2, false)

This branches into many possibilities...

Optimal path:
Day 0 (price=3): skip
Day 1 (price=3): skip
Day 2 (price=5): skip
Day 3 (price=0): buy (transactions_left=2, holding=true) → profit = -0 = 0
Day 4 (price=0): hold
Day 5 (price=3): sell (transactions_left=1, holding=false) → profit = 0 + 3 = 3
Day 6 (price=1): buy (transactions_left=1, holding=true) → profit = 3 - 1 = 2
Day 7 (price=4): sell (transactions_left=0, holding=false) → profit = 2 + 4 = 6

Result: 6

Why is it Slow?

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

For n days with k transactions, there are O(n × k × 2) possible states, but pure recursion explores them exponentially.

Complexity:

• Time: Exponential - each state branches into 2-4 choices
• Space: O(n) - recursion stack depth

---

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

The Intuition

Key Insight: Cache results for each (day, transactions_left, holding) state.

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

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

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

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

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

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

Working backwards (conceptually):

Base cases:
- All memo[7][*][*] depend on day 8 which returns 0
- memo[any][0][*] = 0 (no transactions left)

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

memo[7][1][1]: day 7, 1 transaction left, holding
  sell = 4 + 0 = 4
  hold = 0
  → max(4, 0) = 4

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

... (continue building up)

Final: memo[0][2][0] = 6

Memoization Table Structure:

For prices = [3,3,5,0,0,3,1,4]:

memo[day][transactions][holding]:
We have 8 days × 3 transaction states (0,1,2) × 2 holding states = 48 total states

Key states:
memo[3][2][0] = 6  (buy at 0, optimal from here)
memo[5][1][0] = 3  (after first transaction, optimal from here)
memo[0][2][0] = 6  (final answer)

Each state computed at most once!

Complexity:

• Time: O(n × k × 2) = O(n) for k=2 - each state computed once
• Space: O(n × k × 2) 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, tracking all states.

State: dp[i][t][h] = max profit on day i with t transactions left, in holding state h

• dp[i][t][0] = not holding
• dp[i][t][1] = holding

Transition:

// Not holding on day i with t transactions left:
dp[i][t][0] = max(
    dp[i-1][t][0],              // already not holding (skip)
    dp[i-1][t][1] + prices[i]   // sell today (completes transaction, but don't decrement here)
)

// Holding on day i with t transactions left:
dp[i][t][1] = max(
    dp[i-1][t][1],              // already holding (hold)
    dp[i-1][t][0] - prices[i]   // buy today (starts transaction)
)

Wait, there's a subtlety: When do we decrement the transaction count?

Option 1: Decrement when selling (what we did in recursion) Option 2: Decrement when buying (common in tabulation)

Let's use Option 2 for tabulation (decrement on buy):

public int maxProfit(int[] prices) {
    int n = prices.length;
    // dp[day][transactions_completed][holding]
    int[][][] dp = new int[n][3][2];

    // Base case: day 0
    // Can't have completed transactions on day 0
    dp[0][0][0] = 0;              // no transaction, not holding
    dp[0][0][1] = -prices[0];     // no transaction completed, but holding (bought)
    dp[0][1][0] = Integer.MIN_VALUE / 2;  // impossible
    dp[0][1][1] = Integer.MIN_VALUE / 2;  // impossible
    dp[0][2][0] = Integer.MIN_VALUE / 2;  // impossible
    dp[0][2][1] = Integer.MIN_VALUE / 2;  // impossible

    for (int i = 1; i < n; i++) {
        for (int t = 0; t <= 2; t++) {
            // Not holding with t transactions completed
            if (t > 0) {
                // Either already not holding, or sell today (completes transaction t)
                dp[i][t][0] = Math.max(
                    dp[i-1][t][0],           // already not holding
                    dp[i-1][t-1][1] + prices[i]  // sell (completes transaction from t-1 to t)
                );
            } else {
                // t=0: just carry forward or can't sell (no transaction to complete)
                dp[i][t][0] = dp[i-1][t][0];
            }

            // Holding with t transactions completed
            dp[i][t][1] = Math.max(
                dp[i-1][t][1],           // already holding
                dp[i-1][t][0] - prices[i]  // buy today (starts new transaction)
            );
        }
    }

    // Answer: max of not holding with 0, 1, or 2 transactions completed
    return Math.max(dp[n-1][0][0], Math.max(dp[n-1][1][0], dp[n-1][2][0]));
}

Actually, let me use a cleaner approach with k transactions:

public int maxProfit(int[] prices) {
    int n = prices.length;
    if (n == 0) return 0;

    int k = 2;  // at most 2 transactions
    int[][][] dp = new int[n][k + 1][2];

    // Initialize base case
    for (int t = 0; t <= k; t++) {
        dp[0][t][0] = 0;           // not holding on day 0
        dp[0][t][1] = -prices[0];  // holding on day 0 (bought)
    }

    for (int i = 1; i < n; i++) {
        for (int t = 0; t <= k; t++) {
            // Not holding: either already not holding, or sell today
            if (t > 0) {
                dp[i][t][0] = Math.max(
                    dp[i-1][t][0],              // already not holding
                    dp[i-1][t-1][1] + prices[i]  // sell (completes transaction)
                );
            } else {
                dp[i][t][0] = dp[i-1][t][0];
            }

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

    // Return best result with any number of completed transactions
    int maxProfit = 0;
    for (int t = 0; t <= k; t++) {
        maxProfit = Math.max(maxProfit, dp[n-1][t][0]);
    }
    return maxProfit;
}

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

Day 0: price = 3
dp[0][0][0] = 0,  dp[0][0][1] = -3
dp[0][1][0] = 0,  dp[0][1][1] = -3
dp[0][2][0] = 0,  dp[0][2][1] = -3

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

t=1:
  dp[1][1][0] = max(dp[0][1][0], dp[0][0][1] + 3) = max(0, 0) = 0
  dp[1][1][1] = max(dp[0][1][1], dp[0][1][0] - 3) = max(-3, -3) = -3

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

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

t=1:
  dp[2][1][0] = max(0, -3 + 5) = 2
  dp[2][1][1] = max(-3, 0 - 5) = -3

t=2:
  dp[2][2][0] = max(0, -3 + 5) = 2
  dp[2][2][1] = max(-3, 0 - 5) = -3

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

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

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

... (continue for remaining days)

Final result: dp[7][2][0] = 6

Complexity:

• Time: O(n × k × 2) = O(n) for k=2
• Space: O(n × k × 2) = O(n) for k=2

---

Quick Comparison

Feature	Pure Recursion	Memoization	Tabulation
Structure	Recursive	Recursive + cache	Loop + 3D array
Direction	Top-down	Top-down	Bottom-up
Time	Exponential	O(n × k)	O(n × k)
Space	O(n) stack	O(n × k) memo + stack	O(n × k) array
Dimensions	3 (day, transactions, holding)	3 (cached)	3 (explicit)
When to use	Never (too slow)	Learning 3D DP	Production code

---

The Evolution

Approach 1 → Approach 2:

// Add 3D memoization
if (memo[day][transactions][holding] != null) {
    return memo[day][transactions][holding];
}

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

Approach 2 → Approach 3:

// Replace recursion with 3 nested loops
for (int day = 1; day < n; day++) {
    for (int t = 0; t <= k; t++) {
        for (int holding = 0; holding <= 1; holding++) {
            dp[day][t][holding] = ... // compute from previous day
        }
    }
}

---

Mental Models

Pure Recursion: "At each day, explore all possible actions based on transactions left and holding status. Creates a massive decision tree."

Memoization: "Same exploration, but remember every (day, transactions, holding) triple I've already solved."

Tabulation: "Build a 3D table systematically: for each day, for each transaction count, for each holding status, compute the best profit."

---

State Machine Visualization

For k=2 transactions:

State Space (3D):
┌─────────────────────────────────────────────┐
│ Day i, Transaction Count t, Holding Status h│
└─────────────────────────────────────────────┘

At each day:
  For t=0 (no transactions left):
    - Can only skip or sell if holding

  For t=1 (1 transaction left):
    ┌──────────────┐         ┌──────────────┐
    │ Not Holding  │ ──buy──→│   Holding    │
    │   t=1, h=0   │         │   t=1, h=1   │
    └──────────────┘         └──────────────┘
           ↑                        │
           └──────sell (t→0)────────┘

  For t=2 (2 transactions left):
    ┌──────────────┐         ┌──────────────┐
    │ Not Holding  │ ──buy──→│   Holding    │
    │   t=2, h=0   │         │   t=2, h=1   │
    └──────────────┘         └──────────────┘
           ↑                        │
           └──────sell (t→1)────────┘

---

Which Approach to Use?

Use Pure Recursion when:

• ❌ Never in production - exponential time
• ✅ Only for initial understanding
• ✅ Helps visualize the 3D state space

Use Memoization when:

• ✅ You want to think recursively
• ✅ Learning 3D DP concepts
• ✅ Natural extension from 2D state machine

Use Tabulation when:

• ✅ Production code - clearest and most efficient
• ✅ You understand the state transitions
• ✅ Want to see the full DP table structure

---

Complete Working Example

public class BestTimeToBuySellStockIII {

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

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

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

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

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

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

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

    // Approach 3: Tabulation
    public int maxProfitDP(int[] prices) {
        int n = prices.length;
        if (n == 0) return 0;

        int k = 2;  // at most 2 transactions
        int[][][] dp = new int[n][k + 1][2];

        // Base case: day 0
        for (int t = 0; t <= k; t++) {
            dp[0][t][0] = 0;
            dp[0][t][1] = -prices[0];
        }

        for (int i = 1; i < n; i++) {
            for (int t = 0; t <= k; t++) {
                // Not holding
                if (t > 0) {
                    dp[i][t][0] = Math.max(
                        dp[i-1][t][0],
                        dp[i-1][t-1][1] + prices[i]
                    );
                } else {
                    dp[i][t][0] = dp[i-1][t][0];
                }

                // Holding
                dp[i][t][1] = Math.max(
                    dp[i-1][t][1],
                    dp[i-1][t][0] - prices[i]
                );
            }
        }

        int maxProfit = 0;
        for (int t = 0; t <= k; t++) {
            maxProfit = Math.max(maxProfit, dp[n-1][t][0]);
        }
        return maxProfit;
    }

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

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

        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
    }
}

---

Common Pitfalls

Pitfall 1: When to decrement transaction count

// WRONG - decrement on buy in recursion
if (holding) {
    buy = -prices[day] + helper(day+1, transactions-1, true);
}

// RIGHT - decrement on sell (completes the transaction)
if (holding) {
    sell = prices[day] + helper(day+1, transactions-1, false);
}

Pitfall 2: Base case for impossible states

// WRONG - using 0 for impossible states
dp[0][1][0] = 0;  // can't have 1 completed transaction on day 0

// RIGHT - use large negative value
dp[0][1][0] = Integer.MIN_VALUE / 2;

Pitfall 3: Forgetting to check all end states

// WRONG - only checking k transactions
return dp[n-1][k][0];

// RIGHT - check all possible transaction counts
int maxProfit = 0;
for (int t = 0; t <= k; t++) {
    maxProfit = Math.max(maxProfit, dp[n-1][t][0]);
}
return maxProfit;

Pitfall 4: Transaction count confusion

// Clarify: Are we tracking
// - transactions COMPLETED? (what we used)
// - transactions REMAINING?
// Be consistent throughout!

---

Practice Extensions

Once you master these approaches, try:

1. Best Time to Buy and Sell Stock I (LC 121): Only 1 transaction (k=1)
2. Best Time to Buy and Sell Stock II (LC 122): Unlimited transactions (k=∞)
3. Best Time to Buy and Sell Stock IV (LC 188): Generalize to k transactions
4. Best Time to Buy and Sell Stock with Cooldown (LC 309): Add cooldown state
5. Best Time to Buy and Sell Stock with Transaction Fee (LC 714): Add transaction cost

---

Key Takeaways

THE 3D STATE MACHINE

Pure Recursion: Explore all possibilities in 3D space

• Think: "Try all actions considering day, transactions left, and holding status"
• Use: Only for understanding

Memoization: Cache the 3D state space

• Think: "Remember every (day, transactions, holding) result"
• Use: Learning 3D DP

Tabulation: Build 3D table systematically

• Think: "For each day, for each transaction count, for each holding status"
• Use: Production code

Key insight: Adding the transaction limit creates a 3rd dimension in the state space. We're now tracking:

1. Position (day)
2. Mode (holding/not holding)
3. Resource (transactions remaining)

This combines state machine DP (Pattern 5) with resource constraints (Pattern 3)!

---

The Big Picture

Best Time to Buy and Sell Stock III is a 3D state machine DP problem.

Master it, and you'll understand:

• How to add resource constraints to state machines
• 3D DP state spaces
• Transaction counting strategies
• Generalization to arbitrary k (Stock IV)

This is your 3D state machine foundation. Build it strong.