Hard Problemsstocksoptimization

Stock Buy and Sell – At Most 2 Times

Given a stock's price on each of n days and a limit of at most two 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, 3, 5, 0, 0, 3, 1, 4]

Expected output

6

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[s][d] is the most cash you can be up at the end of day d while standing in position s, counting a purchase as minus its price and a sale as plus its price. There are five positions, one per row: 0, no share bought yet; 1, holding your first share; 2, first share sold and not holding; 3, holding your second share; 4, second share sold. The rows are LAYERS of one walk: you can only move down them, one row at a time, and each move down is a buy or a sell. The cell holds an amount of cash and nothing about which days you traded on.

dp[s][d] = max(dp[s][d - 1], dp[s - 1][d - 1] - prices[d]) for s = 1, 3 (a buy); dp[s][d] = max(dp[s][d - 1], dp[s - 1][d - 1] + prices[d]) for s = 2, 4 (a sell)

Ask what you did on day d, given that you end it in position s. Either nothing, and you were already in position s at the end of day d - 1, with exactly the cash you had then; or you made the one move that leads INTO s, from the row above it, paying today's price if that move is a buy and collecting it if it is a sell. Those are the only two ways to be in s tonight, so take the larger. It is the skip-or-take choice the house-robber lesson derives, with "skip" meaning wait a day; this page assumes that lesson and goes straight to the table. Every cell below row 0 has exactly these two candidates, which is why those four rows share one rule and differ only in the sign of the price.

Row 0 is 0 on every day: a walk that has bought nothing has spent nothing. Day 0 is given down the column: holding the first share on day 0 means you bought it at day 0's price, so dp[1][0] = -prices[0]; sold 1 is 0, since buying and selling on the same day gains nothing; hold 2 is -prices[0] again, the first trade done for nothing and the second share bought the same day; sold 2 is 0. Every other cell reads only the column to its left, so the table fills one whole day at a time, rows 1 to 4 top to bottom. That is the order the animation uses.

Tabulation, column by column. Nothing is skipped by a top-down solve here: every row on every day is a position some walk can be in. Because a day reads only the day before, and row 0 never changes, four numbers are all you ever need, and most published answers keep exactly four variables, one per row below row 0. The table is the long-hand version of those variables, so you can watch each one being overwritten. The answer is the bottom-right cell, cash after the second sale on the last day; ending with one trade or none is already counted there, because the day 0 bases treat an unused trade as a free round trip on day 0.

Time O(n), four cells per daySpace O(n) for the table, O(1) with four rolling variables

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 0 on every day: a walk that has bought nothing has spent nothing. Day 0 is given down the column: holding the first share on day 0 means you bought it at day 0's price, so dp[1][0] = -prices[0]; sold 1 is 0, since buying and selling on the same day gains nothing; hold 2 is -prices[0] again, the first trade done for nothing and the second share bought the same day; sold 2 is 0. Every other cell reads only the column to its left, so the table fills one whole day at a time, rows 1 to 4 top to bottom. That is the order the animation uses.

Rows ↓
Cols →

3

5

0

3

1

4

nothing yet

0

hold 1

-3

0

sold 1

0

2

3

4

hold 2

-3

2

sold 2

0

2

5

6

Rows ↓position

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

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

1function maxProfitTwice(prices) {
2 const n = prices.length;
3 // rows: 0 nothing yet, 1 hold first, 2 sold first, 3 hold second, 4 sold second
4 const dp = Array.from({ length: 5 }, () => new Array(n).fill(0));
5 dp[1][0] = dp[3][0] = -prices[0];
6 for (let d = 1; d < n; d++) {
7 for (let s = 1; s <= 4; s++) {
8 const move = s % 2 === 1 ? -prices[d] : prices[d];
9 dp[s][d] = Math.max(dp[s][d - 1], dp[s - 1][d - 1] + move);
10 }
11 }
12 return dp[4][n - 1];
13}

Base caseComputedBeing readAnswer

The code, the trap, the variations

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

1function maxProfitTwice(prices) {
2 const n = prices.length;
3 // rows: 0 nothing yet, 1 hold first, 2 sold first, 3 hold second, 4 sold second
4 const dp = Array.from({ length: 5 }, () => new Array(n).fill(0));
5 dp[1][0] = dp[3][0] = -prices[0];
6 for (let d = 1; d < n; d++) {
7 for (let s = 1; s <= 4; s++) {
8 const move = s % 2 === 1 ? -prices[d] : prices[d];
9 dp[s][d] = Math.max(dp[s][d - 1], dp[s - 1][d - 1] + move);
10 }
11 }
12 return dp[4][n - 1];
13}

Where people go wrong

Taking the single best trade first and then adding the best trade you can fit around it. On prices 1, 5, 2, 8 the best single trade is 1 to 8 for 7, and nothing fits outside it, so that method answers 7; the true best is 1 to 5 and then 2 to 8, for 4 + 6 = 10. The best pair of trades can split the best single trade in two, so a correct method has to choose both trades together, as this table does, or try every day on which to split them. The second trap is in the bases: start the two holding rows at 0 instead of -prices[0] and day 0 hands you a share for free. On the eight-day example that answers 9 instead of 6, for instance by selling the free share at 5 and then trading 0 to 4.

Allow at most k trades instead of two.
The walk grows to 2k + 1 rows, a hold row and a sold row per trade, and every cell keeps the same two candidates. Nothing about the order changes. stock-buy-and-sell-at-most-k-times builds a different table for the same question, one row per trade allowance, which is worth comparing with this one.
Charge a fixed fee on every sale.
Only the sell candidate changes, to dp[s - 1][d - 1] + prices[d] - fee. The five rows, the bases and the day-by-day order stay exactly as they are.
Allow any number of trades.
The rows stop counting trades. Two rows are enough, holding and not holding, each reading the other one day back: with nothing left to count, a sale moves you straight back to the not-holding row instead of further down.
Require a one-day cooldown after every sale.
The buy candidate reads the sold row two days back instead of one, since the day right after a sale cannot be a buy; on day 1, where there is no column two days back, read it as 0. The state and the two-candidate shape are unchanged.

Stock Buy and Sell – At-Most k Times Min cost to sort strings using Reversals