Best Time to Buy and Sell Stock IV

hard dp stocks

Problem

You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k. Find the maximum profit you can achieve. You may complete at most k transactions.

Inputk = 2, prices = [3,2,6,5,0,3]

Output7

Generalize the two-trade trick: maintain best cost b[t] and best profit s[t] for each trade index t = 1..k. Update b[t] using s[t−1] − price, then update s[t] using price − b[t].

prices

def max_profit(k, prices):
    if not prices or k == 0: return 0
    b = [float('inf')] * (k + 1)
    s = [0] * (k + 1)
    for p in prices:
        for t in range(1, k + 1):
            b[t] = min(b[t], p - s[t-1])
            s[t] = max(s[t], p - b[t])
    return s[k]

function maxProfit(k, prices) {
  if (!prices.length || k === 0) return 0;
  const b = new Array(k + 1).fill(Infinity);
  const s = new Array(k + 1).fill(0);
  for (const p of prices) {
    for (let t = 1; t <= k; t++) {
      b[t] = Math.min(b[t], p - s[t-1]);
      s[t] = Math.max(s[t], p - b[t]);
    }
  }
  return s[k];
}

class Solution {
    public int maxProfit(int k, int[] prices) {
        if (prices.length == 0 || k == 0) return 0;
        int[] b = new int[k + 1];
        int[] s = new int[k + 1];
        Arrays.fill(b, Integer.MAX_VALUE);
        for (int p : prices) {
            for (int t = 1; t <= k; t++) {
                b[t] = Math.min(b[t], p - s[t-1]);
                s[t] = Math.max(s[t], p - b[t]);
            }
        }
        return s[k];
    }
}

int maxProfit(int k, vector<int>& prices) {
    if (prices.empty() || k == 0) return 0;
    vector<int> b(k + 1, INT_MAX), s(k + 1, 0);
    for (int p : prices) {
        for (int t = 1; t <= k; t++) {
            b[t] = min(b[t], p - s[t-1]);
            s[t] = max(s[t], p - b[t]);
        }
    }
    return s[k];
}

Explanation

This generalizes the two-trade problem to at most k trades. We keep two small arrays indexed by trade number: b[t] is the best effective cost of the t-th buy, and s[t] is the best profit after the t-th sell.

For every price p, we loop trades t = 1..k and update b[t] = min(b[t], p - s[t-1]) then s[t] = max(s[t], p - b[t]). The p - s[t-1] part means the t-th buy is discounted by all the profit already locked in from the first t-1 trades.

So each trade builds on the one before it, the same chaining idea as the two-trade version but repeated k times. b starts at +∞ and s at 0.

The answer is s[k], the best profit using up to k trades. Using fewer trades is fine because the maxes never penalize stopping early.

Example: k = 2, prices = [3,2,6,5,0,3]. Trade 1 buys at 2 and sells at 6 (+4), trade 2 buys at 0 and sells at 3 (+3), so s[2] = 7.

Time: O(n·k) Space: O(k)