Problem overview
The method MaxProfit(int[] prices, int k) receives the price of a stock on each day and the maximum number of transactions allowed. A transaction is one buy followed by one sell. You can hold at most one share at a time, so you must sell before you buy again. The method returns the largest total profit.
In the first example, prices = [2, 4, 1] and k = 2. Buying at 2 and selling at 4 earns 2. Nothing else earns anything, because the price only drops after day 2, so the answer is 2. In the second, prices = [3, 2, 6, 5, 0, 3] with k = 2: buy at 2 and sell at 6 for 4, then buy at 0 and sell at 3 for 3, a total of 7.
Approach: a table over transactions and days
Trying every set of up to k non-overlapping buy and sell pairs grows exponentially. Dynamic programming reduces this by solving smaller versions of the same problem first. Define dp[t, i] as the best profit using at most t transactions during the first i days. The answer is dp[k, n].
To fill dp[t, i], consider the last day, day i. Either no sale happens on that day, or the last transaction ends with a sale on that day.
- No sale on day
i. The profit equals what was already possible without that day,dp[t, i - 1]. It is also never worse than using fewer transactions,dp[t - 1, i]. - Sale on day
i. Choose the dayj < ion which that share was bought. The profit of that transaction is the sell price minus the buy price. Add the best result for the days before the purchase, using one transaction fewer:dp[t - 1, j - 1].
Taking the best over every choice of j gives the table entry. This lesson tries all the values of j with an inner loop, which is simple but slow. The next lesson on this problem removes that loop by keeping a running best.
Step by step
- Store the length.
int n = prices.Length;is used in the table size and the loops. Arrays in C# report their size with theLengthproperty, without parentheses. - Create the table. An
int[,]withk + 1rows andn + 1columns, filled with zeros. Row 0 (no transactions) and column 0 (no days) must stay 0, and they do. - Loop over
tfrom 1 tok. - Loop over
ifrom 1 ton. Both loops start at 1 because the zero row and column are already correct. - Set the starting value of
dp[t, i]to the larger ofdp[t, i - 1]anddp[t - 1, i], usingMath.Max. This covers the case where dayiis not a selling day. - Loop over
jfrom 1 toi - 1, the possible buy days. A buy must come before the sale, sojstays belowi. - Compute the profit of buying on day
jand selling on dayi. Days count from 1, but the array starts at index 0, so the prices areprices[i - 1]andprices[j - 1]. - Update the cell. Buying on day
juses one transaction, and the days before it, 1 toj - 1, may use up tot - 1of them. So the total isdp[t - 1, j - 1] + profit. Keep the larger of that and the current value. - 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) {
for (int i = 1; i <= n; ++i) {
dp[t, i] = Math.Max(dp[t, i - 1], dp[t - 1, i]);
for (int j = 1; j < i; ++j) {
int profit = prices[i - 1] - prices[j - 1];
dp[t, i] = Math.Max(dp[t, i], dp[t - 1, j - 1] + profit);
}
}
}
return dp[k, n];
}
};
C# details:
- Rectangular array.
new int[k + 1, n + 1]creates one block of zeros, indexed withdp[t, i]. It is notint[][]. Math.Maxtakes two arguments. To compare more values, nest calls or use separate statements, as the solution does.- Index shift. The table is indexed by day number (1 to
n), whilepricesuses 0-based positions. Every price read is thereforeprices[day - 1]. - Negative profit is fine. If selling is a loss,
dp[t - 1, j - 1] + profitis smaller than the starting value, andMath.Maxignores it. That is why doing nothing is always an option.
Complexity
Time: O(k * n²). The two outer loops visit k * n cells, and each runs an inner loop of up to n steps.
Space: O(k * n). The table has (k + 1) * (n + 1) integers.
This is fine for modest inputs. Another lesson on this problem replaces the j loop with one running value and reaches O(k * n).
Edge cases and common mistakes
- Empty or one-day input. With no prices or a single price, no sale is possible.
dp[k, n]stays 0. For an empty array,nis 0 and the inner loops do nothing. - Falling prices. For
[5, 4, 3]andk = 3the answer is 0, not a negative number, since you can simply not trade. - More transactions than needed. Extra transactions never hurt, because the table means "at most
t". Starting each cell fromdp[t - 1, i]carries over the better result from fewer transactions. - Off-by-one on days. Using
prices[i]instead ofprices[i - 1]reads one day too far and throwsIndexOutOfRangeExceptionati = n. - Using
dp[t - 1, j]for the earlier days. That would include dayjitself, letting a share be sold and bought on the same day. The purchase dayjmust not be in the earlier part, so the index isj - 1. - Trailing semicolon. The lesson's class ends with
};. A semicolon after a class declaration is allowed in C#, so it compiles.
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.