263. Best Time to Buy and Sell Stock IV

🔗 LeetCode Problem: 188. Best Time to Buy and Sell Stock IV
📊 Difficulty: Hard
🏷️ Topics: Array, Dynamic Programming, State Machines

📋 Problem Statement

You are given an integer array prices where prices[i] is the price of a given stock on the i-th day, and an integer k.

Find the maximum profit you can achieve. You may complete at most k transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Examples

Example 1:

Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. 
Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Total profit is 4 + 3 = 7.

Example 3:

Input: k = 3, prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 1 (price = 3) and sell on day 2 (price = 5), profit = 5-3 = 2.
Then buy on day 3 (price = 0) and sell on day 7 (price = 4), profit = 4-0 = 4.
Total profit is 2 + 4 = 6.
Note: Only 2 out of 3 allowed transactions were used for optimal profit.

Constraints

1 <= k <= 100
1 <= prices.length <= 1000
0 <= prices[i] <= 1000

💡 Implication of constraints: - ✅ At least one day of trading (minimum array size 1) - ✅ Can complete at most k complete transactions (buy + sell = 1 transaction) - ✅ Must sell before buying again (hold at most one share) - ✅ k can be quite large, requiring efficient O(n×k) solution - ✅ Edge case: If k ≥ n/2, it's equivalent to unlimited transactions (Stock II)

🧒 Understanding The Problem (By Hand)

Let Me Work Example 2 Step By Step

k = 2, prices = [3, 2, 6, 5, 0, 3]
                 0  1  2  3  4  5  (day indices)

Rules: 
  - Complete at most k=2 transactions
  - 1 transaction = buy + sell
  - Must sell before buying again
  - Can use fewer than k transactions

Let me trace different strategies:

Strategy 1: Single Transaction (like Stock I)
  Best buy day = 4 (price=0)
  Best sell day = 5 (price=3) 
  Profit = 3 - 0 = 3

Strategy 2: Two Transactions - Greedy Approach
  Take largest two peaks:
  Peak 1: Buy day 1 (2), Sell day 2 (6) → Profit = 4
  Peak 2: Buy day 4 (0), Sell day 5 (3) → Profit = 3
  Total profit = 4 + 3 = 7 ✓ OPTIMAL!

Strategy 3: Alternative Two Transactions
  Transaction 1: Buy day 0 (3), Sell day 2 (6) → Profit = 3
  Transaction 2: Buy day 4 (0), Sell day 5 (3) → Profit = 3
  Total profit = 3 + 3 = 6 < 7 (suboptimal)

What Did I Learn?

Key Insight 1: k transactions can potentially beat fewer transactions
Key Insight 2: Need to track remaining transaction capacity dynamically
Key Insight 3: Can use fewer than k transactions if more profitable
Key Insight 4: When k ≥ n/2, it becomes unlimited transactions problem

Mathematical Pattern:
  Find optimal combination of up to k transactions
  Each transaction must be non-overlapping
  Greedy approach works when k is large enough

🧒 Special Case: Large k Optimization

When k ≥ n/2, Use Unlimited Transactions Approach

Key Observation: Maximum possible transactions in n days = n/2
  (buy on day i, sell on day i+1, repeat)

If k ≥ n/2:
  We can perform as many transactions as we want
  This becomes Stock II problem: sum all positive price differences

Example: k=10, prices=[1,2,3,4,5] (n=5)
  k=10 ≥ n/2=2.5, so k is "unlimited"
  Answer = (2-1) + (3-2) + (4-3) + (5-4) = 4

🚫 Approach 1 — Brute Force Recursion

Thought Process

At each day, we have three pieces of state: - Day index (ind): Current position in prices array - Can buy (buy): Whether we can buy (0) or must sell (1) - Capacity (cap): Number of transactions remaining (0, 1, 2, ..., k)

For each state, we have choices: 1. When we can buy: Skip buying OR buy the stock
2. When we can sell: Skip selling OR sell the stock (decreases capacity)

We'll explore all possibilities recursively and take the maximum profit.

Algorithm / Pseudocode

solve(day, canBuy, capacity, prices):
    if day == n OR capacity == 0: return 0  // No more days or transactions

    if canBuy == 0:  // State: Can buy
        skip = solve(day+1, 0, capacity, prices)    // Don't buy, stay ready
        buy = -prices[day] + solve(day+1, 1, capacity, prices)  // Buy, now holding
        return max(skip, buy)

    else:  // State: Holding stock  
        skip = solve(day+1, 1, capacity, prices)   // Keep holding
        sell = prices[day] + solve(day+1, 0, capacity-1, prices)   // Sell, complete transaction
        return max(skip, sell)

Code

class Solution {
    // Function to find the maximum profit earned using recursion
    private int func(int ind, int buy, int cap, int n, int[] arr) {
        // Base case 
        if (ind == n || cap == 0) {
            return 0;
        }

        int profit = 0;

        // We can buy the stock
        if (buy == 0) { 
            profit = Math.max(
                0 + func(ind + 1, 0, cap, n, arr),                    // Skip buying
                (-1) * arr[ind] + func(ind + 1, 1, cap, n, arr)       // Buy stock
            );
        }

        // We can sell the stock
        if (buy == 1) { 
            profit = Math.max(
                0 + func(ind + 1, 1, cap, n, arr),                    // Keep holding
                arr[ind] + func(ind + 1, 0, cap - 1, n, arr)          // Sell stock (complete transaction)
            );
        }

        return profit;
    }

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

        // Optimization: If k is large enough, use unlimited transactions approach
        if (k >= n / 2) {
            int maxProfit = 0;
            for (int i = 1; i < n; i++) {
                if (prices[i] > prices[i - 1]) {
                    maxProfit += prices[i] - prices[i - 1];
                }
            }
            return maxProfit;
        }

        // Start at day 0, can buy (state 0), with capacity k
        return func(0, 0, k, n, prices);
    }
}

Dry Run

For k = 2, prices = [3, 2, 6] with capacity = 2:

func(0, 0, 2) → Can buy at day 0 (price=3)
├─ Skip: func(1, 0, 2)
│  ├─ Skip: func(2, 0, 2) 
│  │  ├─ Skip: func(3, 0, 2) → 0
│  │  └─ Buy: -6 + func(3, 1, 2) → -6 + 0 = -6
│  │  → max(0, -6) = 0
│  └─ Buy: -2 + func(2, 1, 2)
│     ├─ Hold: func(3, 1, 2) → 0  
│     └─ Sell: 6 + func(3, 0, 1) → 6 + 0 = 6
│     → max(0, 6) = 6
│  → max(0, -2+6) = 4
└─ Buy: -3 + func(1, 1, 2) → ... (similar analysis)

This creates exponential tree with overlapping subproblems...

Time & Space Complexity

⏰ Time: O(2^n) - Each call branches into 2 possibilities
💾 Space: O(n) - Recursion depth

This approach has exponential time complexity due to overlapping subproblems.

⚠️ Approach 2 — Memoization (Top-Down DP)

Thought Process (How did you arrive here)

🎯 The Optimization Insight:

Brute Force Problem: Same subproblems solved repeatedly
                    ↓
Key Observation: func(day, buy, cap) returns same value every time
                    ↓
Solution: Store results in dp[day][buy][cap] table
         Check table before computing
                    ↓
Trade-off: Use O(n × 2 × (k+1)) space to achieve O(n × 2 × (k+1)) time

Algorithm / Pseudocode

1. Create dp[n][2][k+1] initialized with -1
2. Before computing func(day, buy, cap), check if dp[day][buy][cap] != -1
3. If already computed, return dp[day][buy][cap]
4. Otherwise, compute, store, and return: dp[day][buy][cap] = result

Code

class Solution {
    // Function to find the maximum profit earned using memoization
    private int func(int ind, int buy, int cap, int n, int[] arr, int[][][] dp) {
        // Base case 
        if (ind == n || cap == 0) {
            return 0;
        }

        // If the result for this state has already been calculated, return it
        if (dp[ind][buy][cap] != -1) {
            return dp[ind][buy][cap];
        }

        int profit = 0;

        // We can buy the stock
        if (buy == 0) { 
            profit = Math.max(
                0 + func(ind + 1, 0, cap, n, arr, dp),
                (-1) * arr[ind] + func(ind + 1, 1, cap, n, arr, dp)
            );
        }

        // We can sell the stock
        if (buy == 1) { 
            profit = Math.max(
                0 + func(ind + 1, 1, cap, n, arr, dp),
                arr[ind] + func(ind + 1, 0, cap - 1, n, arr, dp)
            );
        }

        // Store the value in dp array and return the calculated profit
        return dp[ind][buy][cap] = profit;
    }

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

        // Optimization: If k is large enough, use unlimited transactions approach
        if (k >= n / 2) {
            int maxProfit = 0;
            for (int i = 1; i < n; i++) {
                if (prices[i] > prices[i - 1]) {
                    maxProfit += prices[i] - prices[i - 1];
                }
            }
            return maxProfit;
        }

        // Declare a DP table to memoize results
        int[][][] dp = new int[n][2][k + 1];

        // Initialize the dp array with -1
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 2; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }

        return func(0, 0, k, n, prices, dp);
    }
}

Dry Run

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

3D DP Table Construction:
══════════════════════════════════════════════════════════════════════════════════════════
Day   Price   dp[day][0][2]   dp[day][1][2]   dp[day][0][1]   dp[day][1][1]   dp[day][0][0]
                (canBuy,cap2)    (holding,cap2)   (canBuy,cap1)    (holding,cap1)   (canBuy,cap0)
══════════════════════════════════════════════════════════════════════════════════════════
 0      3         7              4               3               3        0
 1      2         7              6               3               3        0  
 2      6         7              6               3               3        0
 3      5         3              3               3               0        0
 4      0         3              3               3               3        0
 5      3         0              0               0               0        0

Answer: dp[0][0][2] = 7

Time & Space Complexity

⏰ Time: O(n × 2 × k) - Each state computed once
💾 Space: O(n × 2 × k) + O(n) = O(n × k) - DP table + recursion stack

✅ Approach 3 — Tabulation (Bottom-Up DP)

Thought Process (How did you arrive here)

💡 Eliminating Recursion:

Memoization Limitation: Still uses O(n) recursion stack
                       ↓
Key Insight: Fill DP table iteratively from end to start
            Eliminate recursion overhead
                       ↓
Algorithm: Start from base case, work towards answer
           dp[day] depends only on dp[day+1]
                       ↓
Result: Same time complexity, cleaner implementation

Base Case Derivation (Step by Step)

🤔 The Big Question: What happens when we've processed all days OR used all transactions?

Let's think about this intuitively:

Step 1: Understanding the "No More Days" Scenario

Imagine: prices = [3, 2, 6] and we're at day 3 (beyond last day)

Question: If there are no more days left, what's the maximum profit?
Answer: 0! We can't make any more moves.

Why 0 regardless of our state or remaining capacity?
  - No days left to trade → profit = 0

Conclusion: dp[n][buy][cap] = 0 for all buy and cap values

Step 2: Understanding the "No More Transactions" Scenario

Imagine: We're at day 1 but capacity = 0 (no transactions left)

Question: If we have no transaction capacity left, what's the maximum profit?
Answer: 0! We can't buy or complete any more transactions.

Why 0 regardless of current state?
  - Can't buy: No capacity to complete transaction → profit = 0
  - Holding stock: No capacity to sell → stuck → profit = 0

Conclusion: dp[day][buy][0] = 0 for all day and buy values

Step 3: Base Case in Code

From our recursive logic:
  if (ind == n || cap == 0) return 0;  ← BASE CASE!

This means:
  dp[n][buy][cap] = 0 for all buy, cap
  dp[day][buy][0] = 0 for all day, buy

In tabulation:
  Initialize all dp[n][buy][cap] = 0
  All dp[day][buy][0] are automatically 0 (default initialization)

Algorithm / Pseudocode

1. Create dp[n+1][2][k+1] (extra row for base case)
2. Initialize base case: dp[n][buy][cap] = 0 for all buy, cap
3. Iterate from day (n-1) down to 0:
   For each buy state (0 to 1):
     For each capacity (1 to k):
       Apply same transition logic as recursion:
       - If canBuy: max(skip, buy)
       - If holding: max(hold, sell and reduce capacity)
4. Return dp[0][0][k] (max profit starting from day 0, able to buy, with k transactions)

Code

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

        // Optimization: If k is large enough, use unlimited transactions approach
        if (k >= n / 2) {
            int maxProfit = 0;
            for (int i = 1; i < n; i++) {
                if (prices[i] > prices[i - 1]) {
                    maxProfit += prices[i] - prices[i - 1];
                }
            }
            return maxProfit;
        }

        // Declaring a 3D DP array of size [n+1][2][k+1] initialized to 0
        int[][][] dp = new int[n + 1][2][k + 1];

        // Base case: dp array is already initialized to 0, covering the base case.

        // Iterate backwards through the prices array
        for (int ind = n - 1; ind >= 0; ind--) {

            // buy can be 0 (buying) or 1 (selling)
            for (int buy = 0; buy <= 1; buy++) {

                // cap represents the number of transactions remaining (can be 1 to k)
                for (int cap = 1; cap <= k; cap++) {
                    int profit = 0;

                    // We can buy the stock
                    if (buy == 0) { 
                        profit = Math.max(
                            0 + dp[ind + 1][0][cap],                     // Skip buying
                            (-1) * prices[ind] + dp[ind + 1][1][cap]     // Buy stock
                        );
                    }

                    // We can sell the stock
                    if (buy == 1) { 
                        profit = Math.max(
                            0 + dp[ind + 1][1][cap],                     // Keep holding
                            prices[ind] + dp[ind + 1][0][cap - 1]        // Sell stock (complete transaction)
                        );
                    }

                    dp[ind][buy][cap] = profit;
                }
            }
        }

        // The result is stored in dp[0][0][k] which represents maximum profit after the final transaction.
        return dp[0][0][k];
    }
}

Dry Run

Building DP table for k = 2, prices = [3, 2, 6, 5, 0, 3]:

Bottom-Up 3D Table Construction:
═══════════════════════════════════════════════════════════════════

Step 1: Base case (day 6)
dp[6][buy][cap] = 0 for all buy, cap

Step 2: Day 5 (price = 3)
buy=0, cap=2: max(dp[6][0][2], -3 + dp[6][1][2]) = max(0, -3+0) = 0
buy=0, cap=1: max(dp[6][0][1], -3 + dp[6][1][1]) = max(0, -3+0) = 0
buy=1, cap=2: max(dp[6][1][2], 3 + dp[6][0][1]) = max(0, 3+0) = 3
buy=1, cap=1: max(dp[6][1][1], 3 + dp[6][0][0]) = max(0, 3+0) = 3

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

Step 4: Day 3 (price = 5)
buy=0, cap=2: max(dp[4][0][2], -5 + dp[4][1][2]) = max(3, -5+3) = 3
buy=0, cap=1: max(dp[4][0][1], -5 + dp[4][1][1]) = max(3, -5+3) = 3
buy=1, cap=2: max(dp[4][1][2], 5 + dp[4][0][1]) = max(3, 5+3) = 8
buy=1, cap=1: max(dp[4][1][1], 5 + dp[4][0][0]) = max(3, 5+0) = 5

Continue this pattern...

Final Answer: dp[0][0][2] = 7

Time & Space Complexity

⏰ Time: O(n × 2 × k) = O(n × k)
💾 Space: O(n × 2 × k) = O(n × k)

🎯 Approach 4 — Space Optimized (Final)

Thought Process (How did you arrive here)

🚀 Ultimate Optimization:

Tabulation Observation: dp[day] only depends on dp[day+1]
                       ↓
Space Insight: Don't need entire n×2×(k+1) table
               Only need "current" and "next" day values
                       ↓
Optimization: Use 2D arrays for current and next
              after[buy][cap], ahead[buy][cap]  
                       ↓
Result: Same time O(n×k), space reduced to O(k) since 2×(k+1) depends on k

Algorithm / Pseudocode

1. Initialize: after[buy][cap] = 0 for all buy, cap (base case)
2. For day from n-1 down to 0:
   - For each buy state and capacity:
     - Apply DP transition logic
     - Store result in ahead[buy][cap]
   - Copy ahead to after for next iteration
3. Return ahead[0][k]

Code

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

        // Optimization: If k is large enough, use unlimited transactions approach
        if (k >= n / 2) {
            int maxProfit = 0;
            for (int i = 1; i < n; i++) {
                if (prices[i] > prices[i - 1]) {
                    maxProfit += prices[i] - prices[i - 1];
                }
            }
            return maxProfit;
        }

        // Space optimization: only need next day's values
        int[][] after = new int[2][k + 1];  // after[buy][cap]
        int[][] ahead = new int[2][k + 1];  // current computation

        // Base case: already initialized to 0

        for (int ind = n - 1; ind >= 0; ind--) {
            for (int buy = 0; buy <= 1; buy++) {
                for (int cap = 1; cap <= k; cap++) {
                    int profit = 0;

                    if (buy == 0) { // Can buy
                        profit = Math.max(
                            after[0][cap],                           // Skip buying
                            -prices[ind] + after[1][cap]             // Buy stock
                        );
                    } else { // Holding stock
                        profit = Math.max(
                            after[1][cap],                           // Keep holding  
                            prices[ind] + after[0][cap - 1]          // Sell stock
                        );
                    }

                    ahead[buy][cap] = profit;
                }
            }

            // Copy ahead to after for next iteration
            for (int i = 0; i < 2; i++) {
                for (int j = 0; j <= k; j++) {
                    after[i][j] = ahead[i][j];
                }
            }
        }

        return after[0][k];
    }
}

Time & Space Complexity

⏰ Time: O(n × 2 × k) = O(n × k)
💾 Space: O(2 × (k + 1)) = O(k)

Quick Revision

Quick Implementation

public class Solution {
  public int maxProfit(int k, int[] a) {
    // return recursive(a, 0, 0, k);

    // Integer[][][] memo = new Integer[a.length + 1][2][k + 1];
    // return topDown(a, 0, 0, k, memo);

    return bottomUp(a, k);
  }

  private int bottomUp(int[] a, int kk) {
    int n = a.length;
    int[][][] dp = new int[n + 1][2][kk + 1];

    for (int i = n - 1; i >= 0; i--) {
      for (int canBuy = 0; canBuy <= 1; canBuy++) {
        for (int k = 1; k <= kk; k++) {

          int profit = 0;
          if (canBuy == 0) {
            int skipIt = dp[i + 1][canBuy][k];
            int buyIt = -a[i] + dp[i + 1][1][k];

            profit = Math.max(skipIt, buyIt);
          } else {
            int skipIt = dp[i + 1][canBuy][k];
            int sellIt = a[i] + dp[i + 1][0][k - 1];

            profit = Math.max(skipIt, sellIt);
          }

          dp[i][canBuy][k] = profit;
        }
      }
    }

    return dp[0][0][kk];
  }

  private int topDown(int[] a, int index, int canBuy, int k, Integer[][][] memo) {
    if (index == a.length || k == 0) {
      return 0;
    }

    if (memo[index][canBuy][k] != null) {
      return memo[index][canBuy][k];
    }

    int profit = 0;
    if (canBuy == 0) {
      int skipIt = topDown(a, index + 1, canBuy, k, memo);
      int buyIt = -a[index] + topDown(a, index + 1, 1, k, memo);

      profit = Math.max(skipIt, buyIt);
    } else {
      int skipIt = topDown(a, index + 1, canBuy, k, memo);
      int sellIt = a[index] + topDown(a, index + 1, 0, k - 1, memo);

      profit = Math.max(skipIt, sellIt);
    }

    return memo[index][canBuy][k] = profit;
  }

  private int recursive(int[] a, int index, int canBuy, int k) {
    // step 2: base case
    if (index == a.length || k == 0) {
      return 0;
    }

    int profit = 0;
    // step 1: canBuy = 0 or 1
    // 0 means we can buy (not mandatory. can skip also)
    // 1 means we can sell (not mandatory. can skip also)
    if (canBuy == 0) {
      int skipIt = recursive(a, index + 1, canBuy, k);
      int buyIt = -a[index] + recursive(a, index + 1, 1, k);

      profit = Math.max(skipIt, buyIt);
    } else {
      int skipIt = recursive(a, index + 1, canBuy, k);
      int sellIt = a[index] + recursive(a, index + 1, 0, k - 1);

      profit = Math.max(skipIt, sellIt);
    }

    return profit;
  }

  public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(s.maxProfit(2, new int[] { 3, 2, 6, 5, 0, 3 }) == 7);
  }
}

📝 Edge Cases & Testing

Edge Cases

Single day: [5] → Return 0 (can't buy and sell for profit)
k = 0: Any prices → Return 0 (no transactions allowed)
k = 1: Becomes Stock I problem (single transaction)
k ≥ n/2: Becomes Stock II problem (unlimited transactions)
All same prices: [3, 3, 3] → Return 0 (no profit opportunity)
Monotonic increasing: [1, 2, 3, 4, 5] → Depends on k
Monotonic decreasing: [5, 4, 3, 2, 1] → Return 0 (never buy)

Test Suite

Basic Tests:

assertEquals(2, maxProfit(2, [2,4,1]));           // Example 1
assertEquals(7, maxProfit(2, [3,2,6,5,0,3]));     // Example 2  
assertEquals(6, maxProfit(3, [3,3,5,0,0,3,1,4])); // Example 3

Edge Tests:

assertEquals(0, maxProfit(2, [5]));               // Single element
assertEquals(0, maxProfit(0, [1,2,3,4,5]));       // k = 0
assertEquals(4, maxProfit(1, [1,2,3,4,5]));       // k = 1 (Stock I)
assertEquals(4, maxProfit(10, [1,2,3,4,5]));      // Large k (Stock II)
assertEquals(0, maxProfit(2, [3,3,3,3]));         // All same

Transaction Limit Tests:

assertEquals(2, maxProfit(1, [1,2,1,2]));         // k=1, multiple peaks
assertEquals(2, maxProfit(2, [1,2,1,2]));         // k=2, same input  
assertEquals(7, maxProfit(3, [1,2,4,2,5,7,2,4,9,0])); // k=3, many peaks

Large k Optimization Tests:

int[] prices = {1,2,1,2,1,2,1,2};
assertEquals(maxProfit(4, prices), maxProfit(100, prices)); // Large k same as sufficient k

Stress Tests:

// Large input with optimal k transactions
int[] large = {0, 10, 0, 10, 0, 10}; // 3 clear transactions possible
assertEquals(30, maxProfit(3, large));  // 3 × 10 = 30

// Large input with no profit  
int[] largeDown = new int[1000];
for(int i = 0; i < 1000; i++) largeDown[i] = 1000-i;
assertEquals(0, maxProfit(50, largeDown));

Key Insights

Generalized Problem: Stock IV is the most general form - covers Stock I, II, III
State modeling: Three dimensions [day][buy][capacity] capture all constraints perfectly
Large k optimization: Critical performance improvement for k ≥ n/2 cases
DP progression: Classic recursion → memoization → tabulation → space optimization
Constraint handling: Transaction capacity decreases only on sell (completing a transaction)
Pattern mastery: This 3D DP pattern is the foundation for all stock trading problems

Problem Series Progression

Problem	Constraint	Approach	Complexity
Stock I	1 transaction	Two pointers / DP	O(n) time, O(1) space
Stock II	Unlimited	Greedy / 2D DP	O(n) time, O(1) space
Stock III	2 transactions	3D DP	O(n) time, O(1) space
Stock IV	k transactions	3D DP + optimization	O(n×k) time, O(k) space

Advanced Optimizations

Large k handling: When k ≥ n/2, switch to unlimited transactions
Space optimization: Reduce from O(n×k) to O(k) space
Early termination: If all prices are decreasing, return 0 immediately
Memory efficiency: Use rolling arrays to minimize cache misses

The space-optimized solution achieves optimal O(n×k) time and O(k) space complexity while handling the complex constraint of at most k transactions!