Best time to buy and sell a stock at most K times

Hard

Problem

prices[i] is the price on day i. Complete at most k transactions, never holding more than one share at a time. Return the maximum profit.

Example 1

Input:  k = 2, prices = [3, 2, 6, 5, 0, 3]
Output: 7

Buy at 2, sell at 6; buy at 0, sell at 3.

Also asked as: Maximum profit by buying and selling a share at most k times

Test cases

Case 1

Input:    2, [3,2,6,5,0,3]
Expected: 7

Case 2

Input:    2, [2,4,1]
Expected: 2

Case 3

Input:    1, [7,6,4]
Expected: 0

Case 4

Input:    0, [1,5]
Expected: 0

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. DP over (transactions, day), O(k·n)

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

dp[t][d] = max profit using ≤ t transactions up to day d = max(dp[t][d−1], price[d] + best) where best = max over m<d of (dp[t−1][m] − price[m]) — maintained incrementally.

function maxProfitK(k, prices) {
const n = prices.length;
if (!n) return 0;
if (k >= n / 2) { // unlimited transactions
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 }, () => new Array(n).fill(0));
for (let t = 1; t <= k; t++) {
let best = -prices[0];
for (let d = 1; d < n; d++) {
dp[t][d] = Math.max(dp[t][d - 1], prices[d] + best);
best = Math.max(best, dp[t - 1][d] - prices[d]);
}
}
return dp[k][n - 1];
}