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're given an array of stock prices and an integer k. Find the maximum profit obtainable using at most k buy-sell transactions, where a new transaction can't start until the previous one has been closed out (you must sell before buying again).

Input Format
Implement maxProfit(k, prices). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
k = 2
prices = [2,4,1]
Output
2

Example 2

Input
k = 2
prices = [3,2,6,5,0,3]
Output
7
Constraints
  • 1 <= k <= 100
  • 1 <= prices.length <= 1000
  • 0 <= prices[i] <= 1000
Test Cases (2)
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.

javascript
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