Best Time to Buy and Sell Stock IV Hard 0 attempts
LeetCode ↗

Best Time to Buy and Sell Stock IV

Hard Dynamic ProgrammingMemoization LeetCode

You are given an array of prices and an integer k. Find the maximum profit you can achieve with at most k transactions. You may not engage in multiple transactions simultaneously.

Example: k = 2, prices = [2,4,1] → Output: 2

Sample Input
—
Sample Output
—
Constraints
  • 1 <= k <= 100
  • 1 <= prices.length <= 1000
  • 0 <= prices[i] <= 1000
Test Cases
Case 1
Args: [2,[2,4,1]] Expected: 2
Case 2
Args: [2,[3,2,6,5,0,3]] Expected: 7
Topics
Dynamic ProgrammingMemoization

DP with State Machine

Use dp[t][0/1] to track max profit after t transactions with/without stock.

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

Time: O(nk) | Space: O(k)

Saved in this browser only. Private to you.

JavaScript