Hard Problemsstocksoptimization

Stock Buy and Sell – At-Most k Times

Given a stock's price on each of n days and a limit of at most k buy-sell transactions, where you never hold more than one share at a time and each sell must follow its matching buy, find the maximum total profit achievable.

Do this lesson first: house robber

Example input

prices = [3, 2, 6, 5, 0, 3], k = 2

Expected output

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[t][d] is the most profit you can have made by the end of day d using at most t complete trades, with no share in hand. Two numbers name it, the trade allowance and the day, so the table has one row per allowance from 0 up to k and one column per day. The rows are LAYERS: row t is built entirely out of row t - 1 and its own left neighbour, so the k you pick only decides how many layers get stacked.

dp[t][d] = max(dp[t][d - 1], max over j < d of dp[t - 1][j] + prices[d] - prices[j])

Ask whether anything was sold on day d. If not, day d changed nothing and the answer is dp[t][d - 1]. If so, it closed the last of your trades, which was bought on some earlier day j. That trade earned prices[d] - prices[j], and every OTHER trade, at most t - 1 of them, had to finish by day j, so the best those can add is dp[t - 1][j]. Selling one trade and buying the next on the same day j is allowed; it never helps, since holding through earns the same with one trade fewer. Try every j and keep the best, then compare with not selling at all. It is the wait-or-act choice from the house-robber lesson with a whole row of ways to act; this page assumes that lesson rather than re-deriving it.

Tabulation, row by row. The inner max over j is what makes this O(k × n²), and it is shown long-hand here so every buy day is a visible candidate. In practice you carry one running number per row, the best dp[t - 1][j] - prices[j] seen so far, and the inner loop disappears, giving O(k × n). Once k is at least n / 2 the limit can never bind: consecutive rising stretches are separated by at least one day-to-day step that does not rise, so n days (n - 1 steps) hold at most n / 2 of them, one trade each covers them all, and the answer is simply every day-to-day rise added up. Real solutions check for that first.

Time O(k × n²) as drawn, O(k × n) with a running best per rowSpace O(k × n), reducible to two rows

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

Row 0 is all zeros: with no trades allowed nothing is earned. Column 0 is all zeros: one day cannot hold a buy and a later sale. Every other cell reads its left neighbour and the row above at earlier days, so the table fills one whole row at a time, t = 1 first. That is the order the animation uses, and it is why picking a bigger k just adds rows underneath without changing any row above.

Trades allowed (k)

k = 1k = 2k = 3k = 4

The walkthrough uses this input. Finish it to unlock the others.

Rows ↓
Cols →

t=0

t=1

t=2

Rows ↓trades allowed

Cols →price on each day, day 0 at the left

stock-buy-and-sell-at-most-k-times.ts

1function maxProfitK(prices, k) {
2 const n = prices.length;
3 const dp = Array.from({ length: k + 1 }, () => new Array(n).fill(0));
4 for (let t = 1; t <= k; t++) {
5 for (let d = 1; d < n; d++) {
6 let best = dp[t][d - 1];
7 for (let j = 0; j < d; j++) {
8 best = Math.max(best, dp[t - 1][j] + prices[d] - prices[j]);
9 }
10 dp[t][d] = best;
11 }
12 }
13 return dp[k][n - 1];
14}

Base caseComputedBeing readAnswer

The code, the trap, the variations

stock-buy-and-sell-at-most-k-times.ts

1function maxProfitK(prices, k) {
2 const n = prices.length;
3 const dp = Array.from({ length: k + 1 }, () => new Array(n).fill(0));
4 for (let t = 1; t <= k; t++) {
5 for (let d = 1; d < n; d++) {
6 let best = dp[t][d - 1];
7 for (let j = 0; j < d; j++) {
8 best = Math.max(best, dp[t - 1][j] + prices[d] - prices[j]);
9 }
10 dp[t][d] = best;
11 }
12 }
13 return dp[k][n - 1];
14}

Where people go wrong

Adding up the k biggest day-to-day rises. It feels right, because a trade is a run of rises, but one trade can span several rises and the dips between them. At all ten days with k = 2 the biggest two rises are 4 and 3, so that method answers 7, while the table says 9: buy at 2 and sell at 6, then buy at 0 and hold through the dips to sell at 5. A long trade can be worth more than any single rise inside it, and a table that weighs every buy day, as this one does, sees that. The rises method is guaranteed right only once k is large enough not to bind.

Fix k = 2.
Nothing in this table changes; it just stops at row 2. stock-buy-and-sell-at-most-two-times answers the same question with five rows of positions (nothing yet, hold 1, sold 1, hold 2, sold 2), each cell reading only the day before, which is O(n) with no inner loop.
Charge a fee on every sale.
Each candidate sale becomes dp[t - 1][j] + prices[d] - prices[j] - fee. The rows, the bases and the order are unchanged.
Require a day off after each sale before the next buy.
Earlier trades must now finish by day j - 2, so the candidate reads dp[t - 1][j - 2] (0 when j < 2) instead of dp[t - 1][j]. Everything else stays.
Let k be unlimited.
Drop the t index: one row, dp[d] = max(dp[d - 1], max over j < d of dp[j] + prices[d] - prices[j]), reading its own earlier days instead of a row above. Bases and order are unchanged, and its value is the sum of every positive day-to-day change, the shortcut real solutions take once k reaches n / 2.

Maximum sum rectangle Stock Buy and Sell – At Most 2 Times