Problem overview
The function maxProfit(prices, k) receives the price of a stock on each day, prices[0] being day 1, and a limit k on the number of transactions. A transaction is one purchase followed by one sale. The function returns the largest total profit using at most k transactions. You may hold only one share at a time: the stock must be sold before you buy again.
In the first example, prices = [2, 4, 1] and k = 2. Buying at 2 and selling at 4 earns 2, and no second trade can earn more, so the answer is 2. In the second, prices = [3, 2, 6, 5, 0, 3] and k = 2: buying at 2 and selling at 6 earns 4, then buying at 0 and selling at 3 earns 3, for a total of 7.
Approach: best profit for each budget and prefix of days
Trying every set of buy and sell days grows far too quickly. Instead, solve smaller versions of the same question and reuse them. Let dp[transaction][i] be the best profit using at most transaction transactions during the first i days. Row 0 (no transactions) and column 0 (no days) are always 0, and the answer is dp[k][n].
To compute a cell, consider the last day, day i:
- No sale on day
i. Then the answer is already known from a smaller table cell: the same budget over one day fewer,dp[transaction][i-1]. The celldp[transaction-1][i], one transaction fewer over the same days, is also a valid lower bound, since "at most" allows unused transactions. - A sale on day
i. It closes a purchase made on some earlier dayj(j < i). That trade earnsprices[i-1] - prices[j-1]. Before dayjyou had at mosttransaction - 1transactions to use, and the best result for that isdp[transaction-1][j-1]. Try everyjand keep the best.
The prices array is indexed from 0 while days are numbered from 1, which is why the code subtracts 1 when reading prices.
For the second example the table (rows are the budgets 0, 1 and 2; columns are the days 0 to 6) is:
k=0: [0 0 0 0 0 0 0]
k=1: [0 0 0 4 4 4 4]
k=2: [0 0 0 4 4 4 7]
With one transaction the best is 4 from day 3 onward (buy at 2, sell at 6). With two, the late trade (buy at 0, sell at 3) lifts the total to 7 on day 6.
This is the straightforward version of the idea. It tries every j for every cell. A later lesson on the same problem removes that inner loop by keeping a running best value, which brings the time from O(k * n²) down to O(k * n).
Step by step
- Store the length of
pricesinn, since it appears often. - Build the table with the provided
makeMatrix:k + 1rows andn + 1columns, all zeros. - Loop over budgets
transactionfrom 1 tok, so that smaller budgets are finished first. Row 0 stays 0. - Loop over days
ifrom 1 ton. Column 0 stays 0. - Start from the no-sale value: the larger of
dp[transaction][i-1]anddp[transaction-1][i]. - Loop over the buy day
jfrom 1 toi - 1. - Compute the trade's profit as
prices[i-1] - prices[j-1]. It may be negative. - Combine and keep the best: if
dp[transaction-1][j-1] + profitbeats the current cell, replace it. Withmaxthat is one assignment. - Return
dp[k][n].
The solution in Go
func maxProfit(prices []int, k int) int {
n := len(prices)
dp := makeMatrix(k+1, n+1)
for transaction := 1; transaction <= k; transaction++ {
for i := 1; i <= n; i++ {
dp[transaction][i] = max(dp[transaction][i-1], dp[transaction-1][i])
for j := 1; j < i; j++ {
profit := prices[i-1] - prices[j-1]
dp[transaction][i] = max(dp[transaction][i], dp[transaction-1][j-1]+profit)
}
}
}
return dp[k][n]
}
Go details worth a closer look:
- Built-in
max. Since Go 1.21,maxandminare built in and accept integers directly, so no helper function or import is needed. - Slices of slices. Go has no single call that creates a 2D table.
makeMatrixallocates the outer slice and gives each row its ownmake([]int, n+1), which is zero-filled. Rows are separate slices, so writing todp[1][3]never affects row 2. len(prices)is evaluated once inton. A slice's length is cheap to read, but naming it keeps the index arithmetic readable.- Loop variables.
transaction,iandjare declared in eachforstatement and exist only inside it.profitis a fresh variable on every pass of the inner loop.
Complexity
The three nested loops run about k, n and n times, so the time is O(k * n²). The table has (k + 1) * (n + 1) cells, so the space is O(k * n). Row transaction reads only row transaction - 1 and itself, so two rows would suffice if memory mattered.
Edge cases and common mistakes
- Fewer than two days or
k = 0. No trade is possible, and the answer is 0 straight from the zeroed table. - Prices that only fall. Every
profitis negative, but the starting value from the no-sale options is at least 0, somaxnever selects a losing trade. The answer is 0. - A very large
k. The table allocates a row for every allowed transaction, even though at mostn / 2trades can ever be useful. A hugekwastes memory and time, so capping it atn / 2is a sensible refinement. - Off-by-one in the indices. The profit uses
prices[i-1]andprices[j-1], but the table indexj - 1indp[transaction-1][j-1]means "the firstj - 1days", i.e. everything before the purchase day. - Allowing a sale on the purchase day. The inner loop stops at
j < i. Buying and selling on the same day would earn 0 and consume a transaction for nothing.
Testing
Try ([2, 4, 1], 2), which is 2, and ([3, 2, 6, 5, 0, 3], 2), which is 7. With k = 1 the second input gives 4, as the table shows.