Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Best Time to Buy and Sell Stock IV

HARDProblemSolveExternal Links

Description

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 — that is, you may buy at most k times and sell at most k times.

You may not hold more than one share at a time — you must sell your current stock before buying again. If no profitable transaction exists, return 0.

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. Only one transaction is needed since the array is short and there is only one profitable window.

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 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3. Total profit = 4 + 3 = 7. Both transactions are used to capture two separate price rises.

Example 3

Input: k = 1, prices = [90, 80, 70, 60, 50]

Output: 0

Explanation: Prices strictly decrease every day. No matter when you buy, every future sell price is lower, so no profitable transaction exists. Return 0.

Constraints

  • 1 ≤ k ≤ 100
  • 1 ≤ prices.length ≤ 1000
  • 0 ≤ prices[i] ≤ 1000

Editorial

Brute Force

Intuition

The most direct approach is to explore every possible sequence of buy and sell decisions using recursion. On each day, depending on whether we currently hold a stock or not, we decide:

  • If we don't hold a stock and have transactions remaining: We can either buy today or skip to the next day.
  • If we hold a stock: We can either sell today or skip to the next day.

Think of it like standing at a crossroads every single day. One path says "act" (buy or sell), the other says "wait." We try both paths recursively and pick whichever yields more profit. Each complete buy-sell cycle uses up one of our k transactions.

This exhaustive search guarantees we find the optimal answer because we literally try every possible combination of trades. The downside is that the number of paths grows exponentially with the number of days.

Step-by-Step Explanation

Let's trace through with k = 2, prices = [2, 4, 1]:

Step 1: Start at day 0, holding = false, transactions left = 2.

  • Option A: Buy at price 2 → move to day 1, holding = true, transactions left = 1
  • Option B: Skip → move to day 1, holding = false, transactions left = 2

Step 2 (following Option A): Day 1, holding = true, transactions left = 1.

  • Option A1: Sell at price 4 → profit +4, move to day 2, holding = false, transactions left = 1
  • Option A2: Skip → move to day 2, holding = true, transactions left = 1

Step 3 (following A → A1): Day 2, holding = false, transactions left = 1.

  • Option: Buy at price 1 or skip. Either way, no more days after this.
  • Since day 2 is the last day and even if we buy, we can't sell, profit = 0.
  • Total from this path: -2 (buy) + 4 (sell) + 0 = 2

Step 4 (following A → A2): Day 2, holding = true, transactions left = 1.

  • Option: Sell at price 1 → profit +1, or skip (lose the stock).
  • Selling gives -2 + 1 = -1. Skipping gives -2 + 0 = -2.
  • Best = -1. Not better than path A → A1.

Step 5 (following Option B): Day 1, holding = false, transactions left = 2.

  • Option B1: Buy at price 4 → move to day 2, holding = true, transactions left = 1
  • Option B2: Skip → move to day 2, holding = false, transactions left = 2

Step 6 (following B → B1): Day 2, holding = true.

  • Sell at price 1 → profit = -4 + 1 = -3. Skip → -4. Both worse than 0.

Step 7 (following B → B2): Day 2, holding = false.

  • Buy at price 1, can't sell → 0. Skip → 0.

Result: The best path is buy at day 0, sell at day 1, profit = 2.

Brute Force — Recursive Exploration of Buy/Sell Decisions — Watch how the recursive approach explores different buy and sell decision paths on a small example, evaluating every possible combination to find the maximum profit.

Algorithm

  1. Define a recursive function dfs(day, transactionsLeft, holding):
    • Base case: if day >= n or transactionsLeft == 0, return 0
    • Default: profit = dfs(day + 1, transactionsLeft, holding) (skip today)
    • If holding == true: try selling → profit = max(profit, prices[day] + dfs(day + 1, transactionsLeft, false))
    • If holding == false and transactionsLeft > 0: try buying → profit = max(profit, -prices[day] + dfs(day + 1, transactionsLeft - 1, true))
    • Return profit
  2. Call dfs(0, k, false) to start from day 0, with k transactions, not holding stock

Code

class Solution {
public:
    int dfs(int day, int txnLeft, bool holding, vector<int>& prices) {
        if (day >= prices.size() || txnLeft <= 0)
            return 0;
        
        // Option 1: skip today
        int profit = dfs(day + 1, txnLeft, holding, prices);
        
        if (holding) {
            // Option 2: sell today (completes a transaction)
            profit = max(profit, prices[day] + dfs(day + 1, txnLeft - 1, false, prices));
        } else {
            // Option 2: buy today
            profit = max(profit, -prices[day] + dfs(day + 1, txnLeft, true, prices));
        }
        
        return profit;
    }
    
    int maxProfit(int k, vector<int>& prices) {
        return dfs(0, k, false, prices);
    }
};
class Solution:
    def maxProfit(self, k: int, prices: list[int]) -> int:
        n = len(prices)
        
        def dfs(day: int, txn_left: int, holding: bool) -> int:
            if day >= n or txn_left <= 0:
                return 0
            
            # Option 1: skip today
            profit = dfs(day + 1, txn_left, holding)
            
            if holding:
                # Option 2: sell today (completes a transaction)
                profit = max(profit, prices[day] + dfs(day + 1, txn_left - 1, False))
            else:
                # Option 2: buy today
                profit = max(profit, -prices[day] + dfs(day + 1, txn_left, True))
            
            return profit
        
        return dfs(0, k, False)
class Solution {
    public int maxProfit(int k, int[] prices) {
        return dfs(0, k, false, prices);
    }
    
    private int dfs(int day, int txnLeft, boolean holding, int[] prices) {
        if (day >= prices.length || txnLeft <= 0)
            return 0;
        
        // Option 1: skip today
        int profit = dfs(day + 1, txnLeft, holding, prices);
        
        if (holding) {
            // Option 2: sell today (completes a transaction)
            profit = Math.max(profit, prices[day] + dfs(day + 1, txnLeft - 1, false, prices));
        } else {
            // Option 2: buy today
            profit = Math.max(profit, -prices[day] + dfs(day + 1, txnLeft, true, prices));
        }
        
        return profit;
    }
}

Complexity Analysis

Time Complexity: O(2^n)

At each of the n days, we branch into two choices (act or skip). This creates a binary decision tree of depth n. In the worst case, we explore all 2^n leaf nodes. The transaction limit k prunes some branches, but in the worst case the tree is exponential.

Space Complexity: O(n)

The recursion depth is at most n (one call per day). Each stack frame uses O(1) space, so the call stack uses O(n) total space.

Why This Approach Is Not Efficient

The brute force recursion has O(2^n) time complexity. With n up to 1000, this is astronomically large — far beyond any feasible computation.

The core problem is overlapping subproblems. Many different sequences of buy/sell decisions lead to the exact same state: same day, same number of transactions remaining, same holding status. For example, "skip day 0, skip day 1, buy day 2" and "skip day 0, buy day 1, sell day 1, buy day 2" could both land at (day=3, txn=1, holding=true). The brute force recomputes each of these states from scratch.

Key insight: The state can be fully described by three values: (day, transactionsLeft, holding). There are only n × k × 2 unique states. If we cache the result of each state after computing it once, we eliminate all redundant work. This is memoization — the foundation of dynamic programming.

Better Approach - Memoization DP

Intuition

The recursive structure from the brute force is actually perfect — we just need to avoid recomputing the same states. We add a memo table (or cache) indexed by (day, transactionsLeft, holding). Before computing any state, we check if it's already been solved. If so, we return the cached result immediately.

The state space is three-dimensional:

  • day ranges from 0 to n-1 (n values)
  • transactionsLeft ranges from 0 to k (k+1 values)
  • holding is either 0 or 1 (2 values)

Total unique states: n × (k+1) × 2. Each state is computed exactly once with O(1) work per state (just a few comparisons and additions). This collapses the exponential recursion into a polynomial-time algorithm.

Imagine you're solving a maze where many corridors loop back to the same intersections. The first time you reach an intersection, you explore all paths and write the best result on the wall. Next time you reach the same intersection, you just read the answer off the wall — no re-exploration needed.

Step-by-Step Explanation

Let's trace through with k = 2, prices = [3, 2, 6, 5, 0, 3]:

Step 1: Call dfs(0, 2, false). Day 0, price=3. Not holding, 2 txns left.

  • Skip → dfs(1, 2, false)
  • Buy → -3 + dfs(1, 1, true)
  • Need to compute both sub-calls.

Step 2: Computing dfs(1, 2, false). Day 1, price=2. Not holding, 2 txns left.

  • Skip → dfs(2, 2, false)
  • Buy → -2 + dfs(2, 1, true)
  • Explore buying at 2 (cheaper than day 0).

Step 3: Computing dfs(2, 1, true). Day 2, price=6. Holding, 1 txn left.

  • Skip → dfs(3, 1, true)
  • Sell → 6 + dfs(3, 1, false)
  • Selling at 6 after buying at 2 gives profit 4. Explore sell path.

Step 4: Computing dfs(3, 1, false). Day 3, price=5. Not holding, 1 txn left.

  • Skip → dfs(4, 1, false)
  • Buy → -5 + dfs(4, 0, true)
  • Skip leads to better options — buying at day 4 (price 0) is much cheaper.

Step 5: Computing dfs(4, 1, false). Day 4, price=0. Not holding, 1 txn left.

  • Buy → -0 + dfs(5, 0, true) — buying at 0 costs nothing!
  • dfs(5, 0, true): Day 5, price=3. Holding, 0 txns left... but wait, txn=0 means we already used our transaction to buy. We can sell.
  • Sell at 3 → profit = 3.

Step 6: Cache hit! When other recursive paths reach the same state (4, 1, false), we return the cached value 3 instantly.

Step 7: Combining: Best path is buy day 1 (cost 2), sell day 2 (gain 6, profit 4), buy day 4 (cost 0), sell day 5 (gain 3, profit 3). Total = 4 + 3 = 7.

Result: Maximum profit = 7

Memoization DP — Caching States as They're Computed — Watch how the memo table fills as the recursion explores and caches states. Each cell represents the max profit from a given (day, transactions, holding) state.

Algorithm

  1. Create a 3D memo table dp[n][k+1][2] initialized to -1 (uncomputed)
  2. Define dfs(day, txnLeft, holding):
    • If day >= n or txnLeft <= 0, return 0
    • If dp[day][txnLeft][holding] != -1, return cached value
    • Compute: skip = dfs(day+1, txnLeft, holding)
    • If holding: sell = prices[day] + dfs(day+1, txnLeft, false)
    • If not holding: buy = -prices[day] + dfs(day+1, txnLeft-1, true)
    • Store max in dp[day][txnLeft][holding] and return it
  3. Return dfs(0, k, false)

Code

class Solution {
public:
    int dp[1001][101][2];
    
    int dfs(int day, int txnLeft, int holding, vector<int>& prices) {
        if (day >= prices.size() || txnLeft <= 0)
            return 0;
        if (dp[day][txnLeft][holding] != -1)
            return dp[day][txnLeft][holding];
        
        int profit = dfs(day + 1, txnLeft, holding, prices);
        
        if (holding) {
            // sell completes the transaction
            profit = max(profit, prices[day] + dfs(day + 1, txnLeft - 1, 0, prices));
        } else {
            // buy — transaction counted on sell
            profit = max(profit, -prices[day] + dfs(day + 1, txnLeft, 1, prices));
        }
        
        return dp[day][txnLeft][holding] = profit;
    }
    
    int maxProfit(int k, vector<int>& prices) {
        memset(dp, -1, sizeof(dp));
        return dfs(0, k, 0, prices);
    }
};
from functools import cache

class Solution:
    def maxProfit(self, k: int, prices: list[int]) -> int:
        n = len(prices)
        
        @cache
        def dfs(day: int, txn_left: int, holding: int) -> int:
            if day >= n or txn_left <= 0:
                return 0
            
            # Option 1: skip
            profit = dfs(day + 1, txn_left, holding)
            
            if holding:
                # sell completes the transaction
                profit = max(profit, prices[day] + dfs(day + 1, txn_left - 1, 0))
            else:
                # buy — transaction counted on sell
                profit = max(profit, -prices[day] + dfs(day + 1, txn_left, 1))
            
            return profit
        
        return dfs(0, k, 0)
class Solution {
    private int[][][] dp;
    
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        dp = new int[n][k + 1][2];
        for (int[][] layer : dp)
            for (int[] row : layer)
                java.util.Arrays.fill(row, -1);
        return dfs(0, k, 0, prices);
    }
    
    private int dfs(int day, int txnLeft, int holding, int[] prices) {
        if (day >= prices.length || txnLeft <= 0)
            return 0;
        if (dp[day][txnLeft][holding] != -1)
            return dp[day][txnLeft][holding];
        
        int profit = dfs(day + 1, txnLeft, holding, prices);
        
        if (holding == 1) {
            // sell completes the transaction
            profit = Math.max(profit, prices[day] + dfs(day + 1, txnLeft - 1, 0, prices));
        } else {
            // buy — transaction counted on sell
            profit = Math.max(profit, -prices[day] + dfs(day + 1, txnLeft, 1, prices));
        }
        
        return dp[day][txnLeft][holding] = profit;
    }
}

Complexity Analysis

Time Complexity: O(n × k)

There are n × (k+1) × 2 unique states, and each state is computed exactly once. The work per state is O(1) — just a few max comparisons and additions. So total time is O(n × k × 2) = O(n × k).

Space Complexity: O(n × k)

The memo table stores n × (k+1) × 2 entries. Additionally, the recursion call stack can go up to depth n. Total space is O(n × k) for the table plus O(n) for the stack, which is O(n × k) overall.

Why This Approach Is Not Efficient

The memoization approach achieves O(n × k) time, which is already optimal for this problem. However, it has two weaknesses:

  1. Space: The 3D memo table uses O(n × k) space. With n = 1000 and k = 100, that's 200,000 entries — manageable, but we can reduce it.
  2. Recursion overhead: Top-down memoization has function call overhead and uses O(n) stack space. For very deep recursion (n = 1000), this adds latency.

Key insight: When we convert to bottom-up DP and observe that each day's computation only depends on the next day's values, we can reduce the space from a full 3D table to just two 2D layers of size (k+1) × 2. We alternate between a "current" layer and a "next" layer, collapsing O(n × k) space down to O(k).

Optimal Approach - Space-Optimized Bottom-Up DP

Intuition

Instead of recursing from the top and caching, we flip the computation: start from the last day and work backward, building the solution iteratively.

For each day i, we compute the maximum profit for every combination of (transactionsLeft, holding). The key observation is that day i's values depend only on day i+1's values — we never need to look further back. So we only maintain two layers:

  • ahead: the DP values for day i+1 (already computed)
  • curr: the DP values for day i (being computed now)

After computing all states for day i, curr becomes the new ahead, and we move to day i-1. When we finish, ahead[k][1] (starting at day 0, with k transactions, ready to buy) holds the answer.

This is like filling out a spreadsheet column by column from right to left. Each column only references the column immediately to its right. Once you've moved past a column, you don't need it anymore, so you can overwrite it.

As a further optimization: when k ≥ n/2, we can make as many transactions as we want (since each transaction spans at least 2 days). In this case, we can use a simpler greedy approach — just sum up every upward price movement.

Step-by-Step Explanation

Let's trace through with k = 2, prices = [3, 2, 6, 5, 0, 3]:

Step 1: Initialize ahead array

  • ahead = [[0, 0], [0, 0], [0, 0]] (3 rows for txn 0,1,2; 2 cols for holding 0,1)
  • This represents the state after all days are processed (profit = 0 everywhere).

Step 2: Process day 5 (price = 3), compute curr:

  • txn=1, holding=1 (sell): max(ahead[1][1], 3 + ahead[1][0]) = max(0, 3+0) = 3
  • txn=1, holding=0 (buy): max(ahead[1][0], -3 + ahead[0][1]) = max(0, -3+0) = 0
  • txn=2, holding=1 (sell): max(ahead[2][1], 3 + ahead[2][0]) = max(0, 3+0) = 3
  • txn=2, holding=0 (buy): max(ahead[2][0], -3 + ahead[1][1]) = max(0, -3+0) = 0
  • curr = [[0,0], [0,3], [0,3]]. Copy to ahead.

Step 3: Process day 4 (price = 0):

  • txn=1, holding=1: max(3, 0+0) = 3. txn=1, holding=0: max(0, -0+3) = 3
  • txn=2, holding=1: max(3, 0+0) = 3. txn=2, holding=0: max(0, -0+3) = 3
  • ahead = [[0,0], [3,3], [3,3]]

Step 4: Process day 3 (price = 5):

  • txn=1, holding=1: max(3, 5+3) = 8? No — txn=1, sell means 5 + ahead[1][0] = 5+3 = 8... Actually we need to be careful: selling doesn't use txn, so sell goes to ahead[txn][0]. But ahead[1][0] = 3. So 5+3=8? Let me recompute.
  • Actually: txn=1, holding=1 (can sell): max(ahead[1][1]=3, price + ahead[1][0]) = max(3, 5+3) = 8. Wait, that seems off. Let me re-check the recurrence.
  • When selling: profit = prices[i] + ahead[txn-1][1] (after selling, txn decreases and we can buy again)
  • Correction: sell state → curr[t][0] = max(ahead[t][0], prices[i] + ahead[t-1][1])
  • buy state → curr[t][1] = max(ahead[t][1], -prices[i] + ahead[t][0])
  • Day 3: txn=1, sell: max(ahead[1][0]=3, 5+ahead[0][1]=5+0)=max(3,5)=5
  • Day 3: txn=1, buy: max(ahead[1][1]=3, -5+ahead[1][0]=−5+3)=max(3,-2)=3
  • Day 3: txn=2, sell: max(ahead[2][0]=3, 5+ahead[1][1]=5+3)=max(3,8)=8
  • Day 3: txn=2, buy: max(ahead[2][1]=3, -5+ahead[2][0]=−5+3)=max(3,-2)=3
  • ahead = [[0,0], [5,3], [8,3]]

Step 5: Process day 2 (price = 6):

  • txn=1, sell: max(5, 6+ahead[0][1]=6+0)=max(5,6)=6
  • txn=1, buy: max(3, -6+ahead[1][0]=−6+5)=max(3,-1)=3
  • txn=2, sell: max(8, 6+ahead[1][1]=6+3)=max(8,9)=9
  • txn=2, buy: max(3, -6+ahead[2][0]=−6+8)=max(3,2)=3
  • ahead = [[0,0], [6,3], [9,3]]

Step 6: Process day 1 (price = 2):

  • txn=2, buy: max(3, -2+ahead[2][0]=−2+9)=max(3,7)=7
  • txn=2, sell: max(9, 2+ahead[1][1]=2+3)=max(9,5)=9
  • ahead = [[0,0], [6,4], [9,7]]

Step 7: Process day 0 (price = 3):

  • txn=2, buy: max(7, -3+ahead[2][0]=−3+9)=max(7,6)=7
  • ahead[2][1] = 7

Result: ahead[k][1] = ahead[2][1] = 7

Space-Optimized DP — Two-Layer Bottom-Up Computation — Watch how we compute DP values day by day from right to left, maintaining only two layers (current and ahead). Each cell stores the max profit from that state onward.

Algorithm

  1. Edge case: If k >= n/2, use greedy — sum all positive price differences and return
  2. Initialize two 2D arrays ahead and curr, each of size (k+1) × 2, filled with 0
  3. Iterate day from n-1 down to 0:
    • For each txn from 1 to k:
      • curr[txn][1] (buy/can-buy state) = max(ahead[txn][1], -prices[day] + ahead[txn][0])
      • curr[txn][0] (sell/holding state) = max(ahead[txn][0], prices[day] + ahead[txn-1][1])
    • Copy curr to ahead
  4. Return ahead[k][1]

Code

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (n < 2) return 0;
        
        // Optimization: if k >= n/2, unlimited transactions
        if (k >= n / 2) {
            int profit = 0;
            for (int i = 1; i < n; i++) {
                if (prices[i] > prices[i - 1])
                    profit += prices[i] - prices[i - 1];
            }
            return profit;
        }
        
        // ahead[t][b]: max profit from next day onward
        // t = transactions left, b = 1 means can buy, 0 means holding
        vector<vector<int>> ahead(k + 1, vector<int>(2, 0));
        vector<vector<int>> curr(k + 1, vector<int>(2, 0));
        
        for (int i = n - 1; i >= 0; i--) {
            for (int t = 1; t <= k; t++) {
                // Can buy (not holding stock)
                curr[t][1] = max(ahead[t][1], -prices[i] + ahead[t][0]);
                // Holding stock (can sell)
                curr[t][0] = max(ahead[t][0], prices[i] + ahead[t - 1][1]);
            }
            ahead = curr;
        }
        
        return ahead[k][1];
    }
};
class Solution:
    def maxProfit(self, k: int, prices: list[int]) -> int:
        n = len(prices)
        if n < 2:
            return 0
        
        # Optimization: if k >= n/2, unlimited transactions
        if k >= n // 2:
            profit = 0
            for i in range(1, n):
                if prices[i] > prices[i - 1]:
                    profit += prices[i] - prices[i - 1]
            return profit
        
        # ahead[t][b]: max profit from next day onward
        ahead = [[0, 0] for _ in range(k + 1)]
        curr = [[0, 0] for _ in range(k + 1)]
        
        for i in range(n - 1, -1, -1):
            for t in range(1, k + 1):
                # Can buy (not holding stock)
                curr[t][1] = max(ahead[t][1], -prices[i] + ahead[t][0])
                # Holding stock (can sell)
                curr[t][0] = max(ahead[t][0], prices[i] + ahead[t - 1][1])
            ahead = [row[:] for row in curr]
        
        return ahead[k][1]
class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if (n < 2) return 0;
        
        // Optimization: if k >= n/2, unlimited transactions
        if (k >= n / 2) {
            int profit = 0;
            for (int i = 1; i < n; i++) {
                if (prices[i] > prices[i - 1])
                    profit += prices[i] - prices[i - 1];
            }
            return profit;
        }
        
        // ahead[t][b]: max profit from next day onward
        int[][] ahead = new int[k + 1][2];
        int[][] curr = new int[k + 1][2];
        
        for (int i = n - 1; i >= 0; i--) {
            for (int t = 1; t <= k; t++) {
                // Can buy (not holding stock)
                curr[t][1] = Math.max(ahead[t][1], -prices[i] + ahead[t][0]);
                // Holding stock (can sell)
                curr[t][0] = Math.max(ahead[t][0], prices[i] + ahead[t - 1][1]);
            }
            for (int t = 1; t <= k; t++) {
                ahead[t][0] = curr[t][0];
                ahead[t][1] = curr[t][1];
            }
        }
        
        return ahead[k][1];
    }
}

Complexity Analysis

Time Complexity: O(n × k)

We iterate through n days, and for each day we process k transaction values. Each computation is O(1) — just a max of two values. Special case: when k ≥ n/2, we use the greedy approach which is O(n).

Space Complexity: O(k)

We maintain only two 2D arrays of size (k+1) × 2 — the curr and ahead layers. This is O(k) space, a significant improvement over the O(n × k) space of the memoization approach. The greedy special case uses O(1) space.