Best time to buy and sell a stock at most K times
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
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];}