Code Implementation

class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        if n == 0 or k == 0:
            return 0
        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
        dp = [[0] * n for _ in range(k+1)]
        for t in range(1, k+1):
            max_diff = -prices[0]
            for d in range(1, n):
                dp[t][d] = max(dp[t][d-1], prices[d] + max_diff)
                max_diff = max(max_diff, dp[t-1][d] - prices[d])
        return dp[k][n-1]
      

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (n == 0 || k == 0) return 0;
        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;
        }
        vector<vector<int>> dp(k+1, vector<int>(n, 0));
        for (int t = 1; t <= k; ++t) {
            int maxDiff = -prices[0];
            for (int d = 1; d < n; ++d) {
                dp[t][d] = max(dp[t][d-1], prices[d] + maxDiff);
                maxDiff = max(maxDiff, dp[t-1][d] - prices[d]);
            }
        }
        return dp[k][n-1];
    }
};
      

class Solution {
    public int maxProfit(int k, int[] prices) {
        int n = prices.length;
        if (n == 0 || k == 0) return 0;
        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;
        }
        int[][] dp = new int[k+1][n];
        for (int t = 1; t <= k; ++t) {
            int maxDiff = -prices[0];
            for (int d = 1; d < n; ++d) {
                dp[t][d] = Math.max(dp[t][d-1], prices[d] + maxDiff);
                maxDiff = Math.max(maxDiff, dp[t-1][d] - prices[d]);
            }
        }
        return dp[k][n-1];
    }
}
      

var maxProfit = function(k, prices) {
    const n = prices.length;
    if (n === 0 || k === 0) return 0;
    if (k >= Math.floor(n / 2)) {
        let profit = 0;
        for (let i = 1; i < n; ++i) {
            if (prices[i] > prices[i-1]) {
                profit += prices[i] - prices[i-1];
            }
        }
        return profit;
    }
    const dp = Array.from({length: k+1}, () => Array(n).fill(0));
    for (let t = 1; t <= k; ++t) {
        let maxDiff = -prices[0];
        for (let d = 1; d < n; ++d) {
            dp[t][d] = Math.max(dp[t][d-1], prices[d] + maxDiff);
            maxDiff = Math.max(maxDiff, dp[t-1][d] - prices[d]);
        }
    }
    return dp[k][n-1];
};
      

Problem Description

The "Best Time to Buy and Sell Stock IV" problem asks you to maximize your profit by making at most k transactions on a given list of daily stock prices. Each transaction consists of buying and then selling one share of the stock. You must sell the stock before you can buy again (i.e., you cannot hold more than one share at a time).

• You are given an integer k (maximum number of allowed transactions) and an integer array prices where prices[i] is the price of a given stock on day i.
• Return the maximum profit you can achieve by completing at most k transactions.
• You may not engage in multiple transactions at the same time (must sell before buying again).
• If you cannot make any profit, return 0.

Thought Process

At first glance, it seems like you could try every possible combination of buy and sell days to maximize profit, but this would be extremely inefficient, especially as the number of transactions k or the number of days grows.

The key realization is that this problem has overlapping subproblems and optimal substructure, making it suitable for a dynamic programming (DP) approach. The brute-force method would be to try all possible pairs of buy and sell days for each transaction, but this quickly becomes infeasible. Instead, we want to keep track of the best profits for each day and each transaction count, building up solutions from previous results.

Another important insight is that if k is very large (specifically, if k ≥ n/2 where n is the number of days), the problem is equivalent to having unlimited transactions. In this case, you can simply sum all increases in price from one day to the next.

Solution Approach

• Step 1: Handle the Unlimited Transactions Case
  • If k is at least half the number of days, you can make as many transactions as you want. In this case, iterate through the prices array and sum up all positive differences between consecutive days.
• Step 2: Dynamic Programming for Limited Transactions
  • Create a DP table dp where dp[t][d] represents the maximum profit you can make with at most t transactions up to day d.
  • Initialize the table with zeros. For each transaction count t from 1 to k, and for each day d:
    • Use a variable maxDiff to keep track of the maximum value of dp[t-1][m] - prices[m] for all days m before d. This helps you efficiently compute the best "buy" point for the current transaction.
    • For each day d, update dp[t][d] as the maximum of:
      • dp[t][d-1] (not selling today), and
      • prices[d] + maxDiff (selling today after buying at the best prior point).
    • Update maxDiff as you go to always reflect the best possible buy for the next day.
  • After filling the table, dp[k][n-1] will contain the answer.

Example Walkthrough

Let's use k = 2 and prices = [2, 4, 1, 7, 5, 3, 6] as an example.

1. For the unlimited transactions case, since k = 2 and n = 7, k < n/2, so we use DP.
2. Build a DP table dp where dp[t][d] is the max profit with at most t transactions up to day d.
3. For t = 1, we look for the single best buy-sell:
   • Best is buy at 1 (day 2) and sell at 7 (day 3): profit = 6
4. For t = 2, we can do two transactions:
   • First: buy at 2 (day 0), sell at 4 (day 1): profit = 2
   • Second: buy at 1 (day 2), sell at 7 (day 3): profit = 6
   • Total: 2 + 6 = 8
   • Or, buy at 1 (day 2), sell at 7 (day 3): profit = 6, then buy at 3 (day 5), sell at 6 (day 6): profit = 3, total = 6 + 3 = 9
5. The DP will find the best combination, which is 9 in this case.

At each step, the DP table is updated to reflect the best possible profit for each transaction count and day.

Time and Space Complexity

• Brute-force Approach:
  • Would involve trying all possible pairs of buy and sell days for each transaction, leading to exponential time complexity: O(n^2k).
• Optimized DP Approach:
  • Time Complexity: O(k * n), since we fill a table of size (k+1) x n and each entry is computed in O(1) using maxDiff.
  • Space Complexity: O(k * n) for the DP table.
  • If space optimization is applied (not shown here), it can be reduced to O(n).
• Unlimited Transactions Case:
  • Time Complexity: O(n), as we simply iterate through the array once.
  • Space Complexity: O(1).

Summary

The "Best Time to Buy and Sell Stock IV" problem is a classic dynamic programming challenge that requires you to maximize profit with at most k transactions. The key insight is to use a DP table to track the best profit for each transaction count and day, leveraging the optimal substructure of the problem. For large k, the problem simplifies to summing all positive price differences. The optimized DP approach ensures an efficient O(k * n) solution, making it suitable for large inputs and demonstrating the power of dynamic programming for financial optimization problems.