Problem overview
The function maxProfit(prices, k) takes the daily prices of a stock and a limit k on the number of transactions, a transaction being one purchase followed by one sale. It returns the largest profit possible with at most k transactions, holding at most one share at a time.
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 it is 7: buy at 2 and sell at 6 for 4, then buy at 0 and sell at 3 for 3.
Approach: keep the best purchase instead of searching for it
The table is the same as in the slower solution to this problem. Let dp[transaction][i] be the best profit with at most transaction transactions in the first i days, and the answer is dp[k][n]. The slower version fills each cell by trying every earlier buy day j in an inner loop, which makes the total time O(k * n²).
The inner loop can go. When day i is a sale day, the candidate profit for a purchase on day j is the profit from earlier trades plus the price difference:
dp[transaction-1][j] - prices[j-1] + prices[i-1]
Only the first two terms depend on j, and the last one depends only on i. So for a fixed transaction, a single number is enough to represent every possible purchase day: the maximum of dp[transaction-1][j] - prices[j-1] over the days seen so far. This lesson calls it maxDiff. At each day i, the best sale-today option is just maxDiff + prices[i-1], found in constant time.
One detail: using dp[transaction-1][j] (the first j days) rather than the first j - 1 days lets a purchase follow a sale on the same day. That is harmless, because a sale and a repurchase on the same day followed by a later sale earn the same as a single longer trade, which uses fewer transactions.
For the second example with transaction = 2, maxDiff after days 1 to 6 is -3, -2, -2, -1, 4, 4. On day 6 the sale option is 4 + 3 = 7. The row dp[2] reads [0 0 0 4 4 4 7].
Step by step
- Store
nas the length ofprices. - Build the table with
makeMatrix(k+1, n+1), all zeros. - Loop over budgets
transactionfrom 1 tok. Row 0 stays zero. - Declare
maxDiffat the start of each budget's pass, before the day loop. It starts atmath.MinInt, the smallestint, because no purchase has been seen yet and any real candidate must beat it. Starting at 0 would pretend that a free purchase exists. - Loop over days
ifrom 1 ton. - Fill the cell with the best of three options: no sale today (
dp[transaction][i-1]), one transaction fewer (dp[transaction-1][i]), or a sale today (maxDiff + prices[i-1]). Two nestedmaxcalls compare the three. - Update
maxDiffafterwards withdp[transaction-1][i] - prices[i-1]. It must come after the cell is computed, so that a stock bought on dayican only be sold on a later day. - 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++ {
maxDiff := math.MinInt
for i := 1; i <= n; i++ {
dp[transaction][i] = max(max(dp[transaction][i-1], dp[transaction-1][i]), maxDiff+prices[i-1])
maxDiff = max(maxDiff, dp[transaction-1][i]-prices[i-1])
}
}
return dp[k][n]
}
Go details worth a closer look:
math.MinIntcomes from themathpackage and is the smallest value ofinton the current platform, which is -9,223,372,036,854,775,808 here. The program needsimport "math". The constant is available since Go 1.17.- Why adding to
math.MinIntis safe on day 1. Integer arithmetic in Go wraps silently on overflow, somath.MinInt + xis only a problem whenxis negative. Prices are not negative, so the sum moves up from the minimum and stays valid. It is also far below any real candidate, so it never wins themax. - Nested
max. The built-inmax(Go 1.21 and later) accepts more than two arguments, somax(a, b, c)would also compile. The reference nests two calls, which does the same thing. :=inside the outer loop. A newmaxDiffis created on every budget, which is what resets it to the minimum for each row.
Complexity
There are two loops of about k and n iterations, and each iteration does constant work, so the time is O(k * n), down from O(k * n²). The table still needs O(k * n) space. Since each row depends only on the row above it, keeping just two rows would cut the space to O(n).
Edge cases and common mistakes
- Resetting
maxDiff. Declaring it once before the budget loop would carry a value from one row into the next. The values come from different rows of the table, so they must not mix. - Updating
maxDiffbefore the cell. With these exact formulas the result would not change, because the extra candidate, buying and selling on dayi, equalsdp[transaction-1][i], which the second option already covers. Keeping the update last still states the rule plainly: a stock bought on dayiis sold on a later day. - Initializing
maxDiffto 0. That treats a free purchase as possible, and on a day-1 sale it would giveprices[0]as profit instead of 0. - No trades possible. With
k = 0, an empty price list or falling prices the answer is 0. - A huge
k. The table still hask + 1rows, although at mostn / 2trades can help. Cappingkatn / 2avoids allocating rows that can never matter.
Testing
The inputs ([2, 4, 1], 2) and ([3, 2, 6, 5, 0, 3], 2) give 2 and 7. This version returns the same answers as the slower one for every input, only faster.