Best Time to Buy and Sell Stock IV
You are given an integer array prices where pricesi is the price of a stock on day i, and an integer k. Find the maximum profit you can achieve with at most k transactions . You must sell before you buy again. This generalizes the two-transaction version: instead of four running numbers, keep two arrays of length k + 1 — buyt and sellt , the best position after buying or selling for the t-th time. On each price, update every transaction level from 1 up to k, each one building on the previous level's sell value. One extra shortcut matters: if k is at least half the number of days, you can never run out of transactions, so the problem collapses to simply summing every price rise — the unlimited-transactions case.
Constraints
- 0 ≤ k ≤ 100
- 0 ≤ prices.length ≤ 1000
- 0 ≤ pricesi ≤ 1000
Example
k = 2, prices = [3, 2, 6, 5, 0, 3]7Explanation Buy on day 1 (price 2), sell on day 2 (price 6), profit 4. Buy on day 4 (price 0), sell on day 5 (price 3), profit 3. Total profit = 4 + 3 = 7.
In plain terms
- Transaction level
- A count of how many buy-sell round trips have happened so far — level 2 means you've already completed one full buy-then-sell and are on your second.
The row is buy and sell for each of the two transaction levels
k=2, so we use the dp arrays (not the unlimited shortcut). day 0, price=3: buy[1]=-3, buy[2]=-3, sells stay 0. All four cells get their first value.
What happens in this step
price = 3 t=1: buy[1] = max(-Infinity, sell[0] - 3 = -3) = -3; sell[1] = max(0, buy[1] + 3 = 0) = 0 t=2: buy[2] = max(-Infinity, sell[1] - 3 = -3) = -3; sell[2] = max(0, buy[2] + 3 = 0) = 0
Steps to visualize
- The row never changes shape: buy1, sell1, buy2, sell2, in that order, for the worked example where k is 2.
- The highlight box covers the cells that changed on the day the step describes.
- If k is large enough to never be a real limit, just sum every day-over-day price increase and stop there.
- Otherwise, keep buyt and sellt for each transaction level t from 1 to k.
- On each price, for every level in order: buyt takes the better of holding its old value or buying today using sell[t-1] as funding.
- sellt takes the better of holding its old value or selling today from buyt.
- After the last price, sellk holds the maximum profit using at most k transactions.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
k=2, so we use the dp arrays (not the unlimited shortcut). day 0, price=3: buy[1]=-3, buy[2]=-3, sells stay 0. All four cells get their first value.
What happens in this step
price = 3 t=1: buy[1] = max(-Infinity, sell[0] - 3 = -3) = -3; sell[1] = max(0, buy[1] + 3 = 0) = 0 t=2: buy[2] = max(-Infinity, sell[1] - 3 = -3) = -3; sell[2] = max(0, buy[2] + 3 = 0) = 0
Solution
function maxProfit(k, prices) {
const n = prices.length;
if (n === 0 || k === 0) {
return 0;
}
if (k >= Math.floor(n / 2)) {
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 buy = new Array(k + 1).fill(-Infinity);
const sell = new Array(k + 1).fill(0);
for (const price of prices) {
for (let t = 1; t <= k; t++) {
buy[t] = Math.max(buy[t], sell[t - 1] - price);
sell[t] = Math.max(sell[t], buy[t] + price);
}
}
return sell[k];
}- Time
- O(n * k)
- Space
- O(k)
Test cases
| Input | Expected | Covers |
|---|---|---|
k = 2, prices = [3, 2, 6, 5, 0, 3] | 7 | example from the docstring |
k = 1, prices = [1, 2] | 1 | smallest valid input: two prices, one transaction |
k = 0, prices = [1, 5, 2, 9] | 0 | k = 0 means no transactions are allowed at all |
k = 2, prices = [] | 0 | no price data means no profit is possible |
k = 100, prices = [2, 4, 1] | 2 | k large enough to trigger the unlimited-transactions shortcut |
k = 2, prices = [9, 7, 5, 3, 1] | 0 | prices only fall, so no transaction is ever profitable |