Problem overview
The method maxProfit(prices, k) receives the price of a stock on each day and a limit k on the number of transactions. A transaction is one buy followed by one sell. You may hold only one share at a time, so you must sell before you buy again. The method returns the largest profit you can make.
In the first example, prices = [2, 4, 1] and k = 2. Buying at 2 and selling at 4 earns 2. Buying at 1 on the last day has no later day to sell, so the answer is 2. In the second example, prices = [3, 2, 6, 5, 0, 3] and k = 2. Buy at 2 and sell at 6 for 4, then buy at 0 and sell at 3 for 3, which totals 7.
Approach: the best profit for t transactions in i days
The brute-force way tries every set of non-overlapping buy and sell day pairs, which grows exponentially. Dynamic programming reuses the answers to smaller questions instead.
Let dp[t][i] be the best profit using at most t transactions during the first i days. Days are counted from 1 here, so the price on day i is prices[i - 1]. For a given cell there are two kinds of choices:
- Day
iis not the day of a sale. Then the answer is no better than what we already had:dp[t][i - 1](the same transactions, one day fewer) ordp[t - 1][i](one transaction fewer). - The last transaction sells on day
i. It bought on some earlier dayj, which earnsprices[i - 1] - prices[j - 1]. Before dayjwe may have used at mostt - 1transactions, worthdp[t - 1][j - 1]. Trying everyjfrom 1 toi - 1and keeping the best total covers every possibility.
Row 0 (no transactions) and column 0 (no days) are always 0, which is why the table starts out filled with zeros. The answer is dp[k][n].
The inner loop over j makes this slower than it needs to be. Another version of this lesson replaces it with a running maximum and gets O(k * n). This one keeps the loop because it is the most direct translation of the idea.
Step by step
- Store the length.
n = prices.lengthis used in several places. - Build the table. It needs
k + 1rows andn + 1columns of zeros.Array.fromwith a function creates each row separately. - Loop over transaction counts
tfrom 1 tok. Row 0 stays 0. - Loop over days
ifrom 1 ton. Column 0 stays 0. - Start with the known best. Set
dp[t][i]to the larger ofdp[t][i - 1]anddp[t - 1][i]. This covers every case without a sale on dayi. - Try every buy day
jfrom 1 toi - 1. The buy must come before the sell. - Compute the profit of buying on day
jand selling on dayi. - Update the cell if that profit plus
dp[t - 1][j - 1]beats the current value. - Return
dp[k][n].
The solution in TypeScript
class Solution {
maxProfit(prices: number[], k: number): number {
const n: number = prices.length;
const dp: number[][] = Array.from({ length: k + 1 }, () => new Array(n + 1).fill(0));
for (let t = 1; t <= k; t++) {
for (let i = 1; i <= n; i++) {
dp[t][i] = Math.max(dp[t][i - 1], dp[t - 1][i]);
for (let j = 1; j < i; j++) {
const profit: number = prices[i - 1] - prices[j - 1];
dp[t][i] = Math.max(dp[t][i], dp[t - 1][j - 1] + profit);
}
}
}
return dp[k][n];
}
}
TypeScript details worth knowing:
Array.from({ length: k + 1 }, () => ...). An object with alengthproperty is enough forArray.fromto produce that many elements, and the second argument builds each one. The function runs once per row, so every row is a new array. The shortcutnew Array(k + 1).fill(new Array(n + 1).fill(0))would store one rowk + 1times, so changing one cell changes the same column in every row.Math.maxtakes any number of arguments and returns a number, so no comparison code is needed.- Annotations are optional.
const n: numberandconst profit: numberrepeat what the compiler already infers. They disappear when the code compiles to JavaScript. - Negative profits are fine.
profitcan be negative when the price falls. Because the cell starts at the previous best and only increases throughMath.max, a losing trade is never chosen. - Doubles, not integers. Prices are
numbervalues, so there is no integer overflow, and ordinary prices add exactly.
Complexity
Time: O(k * n^2). The loops over t, i and j give k times about n times up to n steps.
Space: O(k * n). The table has (k + 1) * (n + 1) cells. Memory grows with k even though more than n / 2 transactions can never help, because each one needs two days.
Edge cases and common mistakes
- No transactions. With
k = 0the table has only row 0, the loops don't run, and the result is 0. - Empty or one-day input. With no prices, or with a single price, nothing can be sold after a buy, so the answer is 0.
- Falling prices.
[7, 6, 4, 3, 1]withk = 3returns 0. Doing nothing is allowed, and "at most" is what makes the table start from 0. - More transactions than useful. With
[3, 2, 6, 5, 0, 3],k = 3andk = 10both return 7, the same ask = 2. The extra allowance changes nothing. - Off-by-one with days. The table counts days from 1, while
pricescounts from 0. That is why the code readsprices[i - 1]anddp[t - 1][j - 1]. - Buying and selling on the same day. Starting
jatiwould add a free zero-profit trade. The loop stops ati - 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.