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

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

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

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

Understanding the Problem

Key constraints:

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

Key insight: This is the generalization of Stock III where k can be any value.

Special case: When k >= n/2 (where n = number of days), we can do unlimited transactions → reduces to Stock II problem!

Important Optimization

Before diving into the approaches, note this critical optimization:

// If k >= n/2, we can do as many transactions as we want
// This is because each transaction takes at least 2 days (buy + sell)
// So if k >= n/2, it's effectively unlimited transactions
if (k >= prices.length / 2) {
    return maxProfitUnlimited(prices);
}

private int maxProfitUnlimited(int[] prices) {
    int profit = 0;
    for (int i = 1; i < prices.length; i++) {
        profit += Math.max(0, prices[i] - prices[i-1]);
    }
    return profit;
}

This optimization is crucial for performance when k is large!

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)

public int maxProfit(int k, int[] prices) {
    if (k >= prices.length / 2) {
        return maxProfitUnlimited(prices);
    }
    return helper(prices, 0, k, false);
}

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

private int maxProfitUnlimited(int[] prices) {
    int profit = 0;
    for (int i = 1; i < prices.length; i++) {
        profit += Math.max(0, prices[i] - prices[i-1]);
    }
    return profit;
}

What Happens with `k=2, prices = [3,2,6,5,0,3]`:

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

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

Result: 7

Why is it Slow?

Overlapping subproblems: States like (day=2, transactions=1, 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
Space: O(n) - recursion stack depth

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

The Intuition

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

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

    // Optimization: if k >= n/2, unlimited transactions
    if (k >= prices.length / 2) {
        return maxProfitUnlimited(prices);
    }

    int n = prices.length;
    // memo[day][transactions_left][holding]
    Integer[][][] memo = new Integer[n][k + 1][2];
    return helper(prices, 0, k, 0, memo);
}

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

private int maxProfitUnlimited(int[] prices) {
    int profit = 0;
    for (int i = 1; i < prices.length; i++) {
        profit += Math.max(0, prices[i] - prices[i-1]);
    }
    return profit;
}

What Happens with `k=2, prices = [3,2,6,5,0,3]`:

Working backwards (conceptually):

Base cases filled first, then work backwards from last day

memo[5][1][1]: day 5, 1 transaction left, holding
  sell = 3 + 0 = 3
  hold = 0
  → 3

memo[4][1][0]: day 4, 1 transaction left, not holding
  buy = -0 + memo[5][1][1] = -0 + 3 = 3
  skip = memo[5][1][0] = 0
  → 3

... (continue building up)

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

Memoization Table Structure:

For k=2, prices = [3,2,6,5,0,3]:

memo[day][transactions][holding]:
6 days × 3 transaction states (0,1,2) × 2 holding states = 36 total states

Key insight: Each state computed at most once!
Time: O(n × k × 2) = O(n × k)

Complexity:

Time: O(n × k) - each of n×k×2 states computed once
Space: O(n × k) memo table + O(n) recursion stack

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

The Intuition

Key Insight: Build solutions from day 0 to day n-1 systematically, for all k values.

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

Transition:

// Not holding on day i with t transactions completed:
if (t > 0) {
    dp[i][t][0] = max(
        dp[i-1][t][0],              // already not holding (skip)
        dp[i-1][t-1][1] + prices[i]  // sell today (completes transaction)
    )
}

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

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

    // Optimization: if k >= n/2, unlimited transactions
    if (k >= n / 2) {
        return maxProfitUnlimited(prices);
    }

    int[][][] dp = new int[n][k + 1][2];

    // Base case: day 0
    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;
}

private int maxProfitUnlimited(int[] prices) {
    int profit = 0;
    for (int i = 1; i < prices.length; i++) {
        profit += Math.max(0, prices[i] - prices[i-1]);
    }
    return profit;
}

What Happens with `k=2, prices = [3,2,6,5,0,3]`:

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

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

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

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

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

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

Result: max(dp[5][0][0], dp[5][1][0], dp[5][2][0]) = max(0, 7, 7) = 7 ✓

Example with k=∞ (k >= n/2):

For k=100, prices = [1,2,3,4,5]:
Since k=100 >= 5/2=2, use unlimited transactions:

profit = (2-1) + (3-2) + (4-3) + (5-4)
       = 1 + 1 + 1 + 1 = 4

This is much faster than O(n × k)!

Complexity:

Time: O(n × k) when k < n/2, O(n) when k >= n/2
Space: O(n × k) dp table

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
k optimization	Yes	Yes	Yes
When to use	Never (too slow)	Learning	Production code

The Evolution

Approach 1 → Approach 2:

// Add 3D memoization with general k
Integer[][][] memo = new Integer[n][k+1][2];

if (memo[day][transactions][holding] != null) {
    return memo[day][transactions][holding];
}

Approach 2 → Approach 3:

// Replace recursion with loops, generalizing for any k
int[][][] dp = new int[n][k+1][2];

for (int i = 1; i < n; i++) {
    for (int t = 0; t <= k; t++) {
        // compute transitions
    }
}

Mental Models

Pure Recursion: "For any k, explore all possible buy/sell decisions at each day, tracking transactions left."

Memoization: "Same exploration, but cache every (day, k, holding) result. Use optimization when k is large."

Tabulation: "Build 3D table for days × transactions × holding. Optimize when k >= n/2 to skip the table entirely."

The k >= n/2 Optimization Insight

WHY k >= n/2 MEANS UNLIMITED TRANSACTIONS

Key insight: Each transaction requires at least 2 days (1 buy + 1 sell).

If we have n days:

Maximum possible transactions = n/2 (buy day 1, sell day 2, buy day 3, sell day 4, ...)

If k >= n/2:

We have more transaction allowance than we could possibly use
This effectively means unlimited transactions
Can use the simple greedy approach from Stock II: buy every dip, sell every peak

Example:

n = 6 days, k = 3
Maximum possible transactions = 6/2 = 3
Since k = 3 = max possible, it's effectively unlimited
Use greedy: profit += max(0, prices[i] - prices[i-1])

Performance impact:

Without optimization: O(n × k) = O(n × 1000000) for large k
With optimization: O(n) for k >= n/2
Massive speedup for large k!

Which Approach to Use?

Use Pure Recursion when:

❌ Never in production - exponential time
✅ Only for initial understanding
✅ Helps visualize the general k state space

Use Memoization when:

✅ You want to think recursively
✅ Learning general 3D DP
✅ Natural extension from Stock III

Use Tabulation when:

✅ Production code - optimal solution
✅ You understand state transitions
✅ Clear generalization from Stock III

Complete Working Example

public class BestTimeToBuySellStockIV {

    // Approach 1: Pure Recursion (SLOW - for understanding only)
    public int maxProfitRecursive(int k, int[] prices) {
        if (k >= prices.length / 2) {
            return maxProfitUnlimited(prices);
        }
        return helperRecursive(prices, 0, k, 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 k, int[] prices) {
        if (prices.length == 0) return 0;
        if (k >= prices.length / 2) {
            return maxProfitUnlimited(prices);
        }

        int n = prices.length;
        Integer[][][] memo = new Integer[n][k + 1][2];
        return helperMemo(prices, 0, k, 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 k, int[] prices) {
        int n = prices.length;
        if (n == 0 || k == 0) return 0;

        if (k >= n / 2) {
            return maxProfitUnlimited(prices);
        }

        int[][][] dp = new int[n][k + 1][2];

        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++) {
                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];
                }

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

    // Helper: Unlimited transactions (k >= n/2)
    private int maxProfitUnlimited(int[] prices) {
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
            profit += Math.max(0, prices[i] - prices[i-1]);
        }
        return profit;
    }

    public static void main(String[] args) {
        BestTimeToBuySellStockIV solution = new BestTimeToBuySellStockIV();

        int[] prices1 = {2, 4, 1};
        int k1 = 2;
        System.out.println("Test 1: k=2, prices=[2,4,1]");
        System.out.println("Pure Recursion: " + solution.maxProfitRecursive(k1, prices1)); // 2
        System.out.println("Memoization: " + solution.maxProfitMemo(k1, prices1));           // 2
        System.out.println("Tabulation: " + solution.maxProfitDP(k1, prices1));              // 2

        int[] prices2 = {3, 2, 6, 5, 0, 3};
        int k2 = 2;
        System.out.println("\nTest 2: k=2, prices=[3,2,6,5,0,3]");
        System.out.println("Pure Recursion: " + solution.maxProfitRecursive(k2, prices2)); // 7
        System.out.println("Memoization: " + solution.maxProfitMemo(k2, prices2));           // 7
        System.out.println("Tabulation: " + solution.maxProfitDP(k2, prices2));              // 7

        int[] prices3 = {1, 2, 3, 4, 5};
        int k3 = 100;  // k >= n/2, use optimization
        System.out.println("\nTest 3: k=100, prices=[1,2,3,4,5] (optimized)");
        System.out.println("Tabulation: " + solution.maxProfitDP(k3, prices3));              // 4
    }
}

Common Pitfalls

Pitfall 1: Forgetting the k >= n/2 optimization

// WRONG - will timeout for large k
public int maxProfit(int k, int[] prices) {
    // directly use 3D DP even when k is huge
}

// RIGHT - check k first
if (k >= prices.length / 2) {
    return maxProfitUnlimited(prices);
}

Pitfall 2: Wrong space allocation for large k

// WRONG - may cause memory error for huge k
int[][][] dp = new int[n][k+1][2];  // if k = 1,000,000 and n = 100

// RIGHT - optimize first
if (k >= n / 2) {
    return maxProfitUnlimited(prices);
}
// Now k < n/2, so space is O(n²)

Pitfall 3: Incorrect transaction counting

// Make sure to be consistent:
// - Decrement on sell (recursion approach)
// - OR track completed transactions (tabulation approach)
// Don't mix both!

Practice Extensions

Once you master these approaches, try:

Best Time to Buy and Sell Stock I (LC 121): k=1
Best Time to Buy and Sell Stock II (LC 122): k=∞ (unlimited)
Best Time to Buy and Sell Stock III (LC 123): k=2
Best Time to Buy and Sell Stock with Cooldown (LC 309): Add cooldown state
Best Time to Buy and Sell Stock with Transaction Fee (LC 714): Subtract fee on each transaction

Key Takeaways

THE GENERAL k SOLUTION

Pure Recursion: Explore 3D state space for any k

Think: "Same as Stock III, but k is now a parameter"
Use: Only for understanding

Memoization: Cache the general 3D state

Think: "Remember every (day, k, holding) combination"
Use: Learning general 3D DP

Tabulation: Build 3D table for any k

Think: "Systematically build for all days, all k values, both holding states"
Use: Production code

Critical optimization: When k >= n/2, use greedy O(n) algorithm instead of O(n×k) DP!

Key insight: Stock IV is the master problem that generalizes all other stock problems:

k=1 → Stock I
k=2 → Stock III
k=∞ (or k>=n/2) → Stock II
Add cooldown → Stock with Cooldown
Add fee → Stock with Transaction Fee

The Big Picture

Best Time to Buy and Sell Stock IV is the generalization of all stock trading problems.

Master it, and you'll understand:

How to generalize from fixed k to arbitrary k
The k >= n/2 optimization trick
When to use DP vs greedy algorithms
3D state space with variable dimensions

This is your general stock trading foundation. Build it strong.

Understanding the Problem​

Important Optimization​

1. Pure Recursion (Unoptimized - Exponential)​

The Intuition​

What Happens with k=2, prices = [3,2,6,5,0,3]:​

Why is it Slow?​

Complexity:​

2. Top-Down DP (Memoization - O(n × k))​

The Intuition​

What Happens with k=2, prices = [3,2,6,5,0,3]:​

Memoization Table Structure:​

Complexity:​

3. Bottom-Up DP (Tabulation - O(n × k))​

The Intuition​

What Happens with k=2, prices = [3,2,6,5,0,3]:​

Example with k=∞ (k >= n/2):​

Complexity:​

Quick Comparison​

The Evolution​

Approach 1 → Approach 2:​

Approach 2 → Approach 3:​

Mental Models​

The k >= n/2 Optimization Insight​

Which Approach to Use?​

Use Pure Recursion when:​

Use Memoization when:​

Use Tabulation when:​

Complete Working Example​

Common Pitfalls​

Pitfall 1: Forgetting the k >= n/2 optimization​

Pitfall 2: Wrong space allocation for large k​

Pitfall 3: Incorrect transaction counting​

Practice Extensions​

Key Takeaways​

The Big Picture​

Understanding the Problem

Important Optimization

1. Pure Recursion (Unoptimized - Exponential)

The Intuition

What Happens with `k=2, prices = [3,2,6,5,0,3]`:

Why is it Slow?

Complexity:

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

The Intuition

What Happens with `k=2, prices = [3,2,6,5,0,3]`:

Memoization Table Structure:

Complexity:

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

The Intuition

What Happens with `k=2, prices = [3,2,6,5,0,3]`:

Example with k=∞ (k >= n/2):

Complexity:

Quick Comparison

The Evolution

Approach 1 → Approach 2:

Approach 2 → Approach 3:

Mental Models

The k >= n/2 Optimization Insight

Which Approach to Use?

Use Pure Recursion when:

Use Memoization when:

Use Tabulation when:

Complete Working Example

Common Pitfalls

Pitfall 1: Forgetting the k >= n/2 optimization

Pitfall 2: Wrong space allocation for large k

Pitfall 3: Incorrect transaction counting

Practice Extensions

Key Takeaways

The Big Picture