Problem overview
The method MaxProfit(int[] prices, int k) takes the stock price on each day and the maximum number of transactions, where a transaction is one buy followed by one sell. You may hold only one share at a time. It returns the largest profit possible.
With prices = [2, 4, 1] and k = 2 the answer is 2: buy at 2, sell at 4. With prices = [3, 2, 6, 5, 0, 3] and k = 2 the answer is 7: buy at 2 and sell at 6 for 4, then buy at 0 and sell at 3 for 3.
Approach: replace the inner loop with a running best
The table is the same as in the slower approach: dp[t, i] is the best profit with at most t transactions in the first i days. That version considered every possible buy day j for each cell, which made the whole algorithm O(k * n²).
The inner loop computes, for a sale on day i, the maximum over earlier days j of
dp[t - 1, j - 1] + prices[i - 1] - prices[j - 1]
The price of the sale day is the same for every j, so it can be taken out of the maximum. What is left, dp[t - 1, j - 1] - prices[j - 1], depends only on j, and the set of allowed values of j only grows as i advances. A single variable can therefore hold the best such value seen so far.
The lesson stores dp[t - 1, j] - prices[j - 1] for each day j, with j rather than j - 1 in the table index. This is still correct: if the earlier work ends with a sale on day j, selling and buying again on the same day gives the same profit as simply holding the share through, so it never beats a real plan. Each cell then costs constant work, and the algorithm runs in O(k * n).
Tracing one row
Take prices = [3, 2, 6, 5, 0, 3] and the row t = 1, where dp[0, i] is always 0. The running value maxDiff is then just the best "minus a price" so far:
day i: 1 2 3 4 5 6
price: 3 2 6 5 0 3
dp[1, i]: 0 0 4 4 4 4
maxDiff: -3 -2 -2 -2 0 0
On day 3, maxDiff is -2 (from buying at 2) and the price is 6, giving a profit of 4. The value then stays at 4 for the rest, because buying at 0 on day 5 and selling at 3 on day 6 earns only 3 in a single transaction.
Step by step
- Store the length in
nfromprices.Length. - Create the table as an
int[,]withk + 1rows andn + 1columns, filled with zeros. Row 0 and column 0 stay 0. - Loop over
tfrom 1 tok. - Declare
maxDiffinside this loop, so each row starts fresh. It holds the best "profit so far minus the price paid" among the days already passed. No day has been seen yet, so it starts atint.MinValue, meaning "nothing available". - Loop over
ifrom 1 ton. - Fill the cell with the best of three options:
dp[t, i - 1](no sale on dayi),dp[t - 1, i](one transaction fewer), andmaxDiff + prices[i - 1](sell today a share bought on the best earlier day). - Update
maxDiffwith today as a possible purchase day:dp[t - 1, i] - prices[i - 1]. This comes after the cell is computed, so a share bought on dayiis never sold on dayi. - Return
dp[k, n].
The solution in C#
class Solution {
public int MaxProfit(int[] prices, int k) {
int n = prices.Length;
int[,] dp = new int[k + 1, n + 1];
for (int t = 1; t <= k; ++t) {
int maxDiff = int.MinValue;
for (int i = 1; i <= n; ++i) {
dp[t, i] = Math.Max(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];
}
};
C# details:
- Starting at
int.MinValueis safe here. On day 1, the expression isint.MinValue + prices[0]. By default C# integers wrap silently on overflow, but a price of 0 or more moves the value up, away from the edge, so nothing wraps. With negative prices it would wrap to a huge positive number and corrupt the answer, so the code relies on non-negative prices. - Why
maxDiffis declared inside thetloop. Each row of the table has its own running best, becausedp[t - 1, ...]changes witht. Declaring it outside would carry stale values into the next row. - Nested
Math.Max. The method compares exactly two numbers, so three options need two calls. - Rectangular array.
int[,]is indexed asdp[t, i], notdp[t][i].
Complexity
Time: O(k * n). Each of the k * n cells takes constant work. The previous O(n) inner loop is gone.
Space: O(k * n). The table has (k + 1) * (n + 1) integers. Row t only reads row t - 1 and itself, so two rows would reduce this to O(n).
Edge cases and common mistakes
- Empty input. With no prices,
nis 0 and the inner loop never runs, so the method returns 0. - Falling prices. For
[5, 4, 3]andk = 3, the sale option is always worse than the carried-over 0, so the answer is 0. - Mixing up the update order. The cell for day
imust use themaxDiffbuilt from earlier days. Here, updating first would only add the candidatedp[t - 1, i], which is already one of the three options, so it would not change the result, but keeping the order makes the reasoning easier to trust. - Declaring
maxDiffoutside thetloop. It would carry values from a different row into the next one. - Initialising
maxDiffto 0. That pretends a share could be bought for free before day 1. A sale would then earn the full price, so[5]withk = 1would return 5 instead of 0. - Index shift. The table is indexed by day number, but
pricesby position, so the price of dayiisprices[i - 1].
Testing
prices = [2, 4, 1],k = 2gives 2.prices = [3, 2, 6, 5, 0, 3],k = 2gives 7.prices = [3, 2, 6, 5, 0, 3],k = 1gives 4.prices = [5, 4, 3],k = 3gives 0.prices = [],k = 2gives 0.