Problem overview
The method maxProfit(prices, k) gets the price of a stock on each day and a limit k on the number of transactions. A transaction is a buy followed by a later sell, and you can hold only one share at a time. The method returns the largest total profit.
For prices = [2, 4, 1] and k = 2 the answer is 2: buy at 2, sell at 4. For prices = [3, 2, 6, 5, 0, 3] and k = 2 the answer is 7: buy at 2 and sell at 6 (profit 4), then buy at 0 and sell at 3 (profit 3).
Approach: replace the inner loop with a running maximum
The straightforward table has dp[t][i] as the best profit with at most t transactions in the first i days. To fill a cell where the last sale happens on day i, it tries every earlier buy day j in a third loop, which costs O(k * n^2) overall.
Look at what that inner loop computes. For a fixed t, the value tried for buy day j is dp[t - 1][j] - prices[j - 1] (the best profit with one fewer transaction up to day j, minus the price paid on day j) and the sale then adds prices[i - 1]. Only the first part depends on j, and it doesn't depend on i at all. So, as i moves forward through the days, we can keep the best value seen so far in one variable, maxDiff, and update it once per day instead of rescanning. Each cell then costs a constant amount of work, and the total drops to O(k * n).
Because the formula uses dp[t - 1][j] and not dp[t - 1][j - 1], it allows a sale and a new buy on the same day. That is harmless: selling and buying again on the same day gives the same profit as simply holding, which uses one transaction fewer, and the table already means "at most".
Here is the table for prices = [3, 2, 6, 5, 0, 3] and k = 2. Column 0 is "no days", and column i is the first i days:
t = 0: [0, 0, 0, 0, 0, 0, 0]
t = 1: [0, 0, 0, 4, 4, 4, 4]
t = 2: [0, 0, 0, 4, 4, 4, 7]
The last cell, 7, is the answer.
Step by step
- Store the length in
n. - Build the table with
k + 1slots, and put a separate row ofn + 1zeros in each, using a loop. Row 0 and column 0 stay 0. - Loop over transaction counts
tfrom 1 tok. - Declare
maxDiffinside that loop, so everytstarts fresh, and set it to negative infinity. No day has been seen yet, so there is no purchase to sell; starting at 0 would pretend you can sell on day 1 without buying. - Loop over days
ifrom 1 ton. - Take the best of three options for
dp[t][i]: no sale on dayi(dp[t][i - 1]), one transaction fewer (dp[t - 1][i]), or sell today the stock bought on the best earlier day (maxDiff + prices[i - 1]). - Update
maxDiffafterward with today's candidatedp[t - 1][i] - prices[i - 1]. The order matters: stock bought today can only be sold on a later day. - Return
dp[k][n].
The solution in TypeScript
class Solution {
maxProfit(prices: number[], k: number): number {
let n = prices.length;
let dp: number[][] = new Array(k + 1);
for (let i = 0; i <= k; ++i) {
dp[i] = new Array(n + 1).fill(0);
}
for (let t = 1; t <= k; ++t) {
let maxDiff = Number.NEGATIVE_INFINITY;
for (let i = 1; i <= n; ++i) {
dp[t][i] = Math.max(dp[t][i - 1], dp[t - 1][i], maxDiff + prices[i - 1]);
maxDiff = Math.max(maxDiff, dp[t - 1][i] - prices[i - 1]);
}
}
return dp[k][n];
}
}
TypeScript details worth knowing:
Number.NEGATIVE_INFINITYis a real value. Anumberis a double, which has infinities built in. Adding a finite number to-Infinitygives-Infinity, so on day 1 the third option can never win. In a language with fixed-size integers, a "minus infinity" has to be a big negative number and can overflow when you add to it. Here that problem doesn't exist.- Separate rows.
new Array(k + 1)creates empty slots, and the loop gives each slot its own array. The alternative of filling the outer array with one row would make all rows share storage. Math.maxwith three arguments compares them all in one call.++iin aforheader behaves exactly likei++there, since the result isn't used.- Types are erased.
number[][]helps the compiler check your code, but it is gone from the JavaScript that runs.
Complexity
Time: O(k * n). Two nested loops, with constant work in each pass: three-way Math.max and one update. This beats the O(k * n^2) of the version with the extra loop.
Space: O(k * n). The table has (k + 1) * (n + 1) cells. Row t only needs row t - 1, so two rows would suffice if memory mattered.
Edge cases and common mistakes
- Starting
maxDiffat 0. It makes the formula act as if a free share were available. On[3, 2, 6, 5, 0, 3]withk = 2that returns 9 instead of 7. - Declaring
maxDiffoutside thetloop. Values from the previous transaction count would leak into the next row. - Updating
maxDiffbefore computing the cell. The candidate for dayiwould then be sold on dayias well, adding exactlydp[t - 1][i], which is already one of the options. The result happens not to change, but the order keeps the logic honest: each candidate comes from an earlier day. k = 0. The loops never run and the answer is 0.- Empty price list. The columns reduce to column 0, and the answer is 0.
- Falling prices.
[7, 6, 4, 3, 1]returns 0, because "at mostk" lets you skip every trade. - Day numbering. The table counts days from 1 and
pricesfrom 0, henceprices[i - 1].
Testing
prices = [2, 4, 1],k = 2gives2.prices = [3, 2, 6, 5, 0, 3],k = 2gives7.prices = [3, 2, 6, 5, 0, 3],k = 1gives4.prices = [7, 6, 4, 3, 1],k = 3gives0.prices = [],k = 2gives0.