Problem overview
The method maxProfit(_ prices: [Int], _ k: Int) takes a list of daily prices and a limit k on transactions, where one transaction is a buy followed by a later sell and you can hold only one share at a time. It returns the largest possible profit.
With [2, 4, 1] and k = 2 the answer is 2. With [3, 2, 6, 5, 0, 3] and k = 2 it is 7: buy at 2 and sell at 6, then buy at 0 and sell at 3.
Approach: replace the buy-day loop with a running maximum
The table is the same as in the slower solution: dp[t][i] is the best profit with at most t transactions in the first i days. The slower version tries every earlier buy day j for every cell, which costs O(k * n^2) overall. This lesson shows that the inner loop is not needed.
When selling on day i, the profit from buying on day j is dp[t - 1][j] - prices[j - 1] + prices[i - 1]. The part dp[t - 1][j] - prices[j - 1] does not depend on i. It says: "if I buy on day j, having already earned dp[t - 1][j], I am down by the price". The best sale on day i uses the largest such value over all earlier days. So instead of searching, keep a variable maxDiff holding the best value seen so far and update it once per day.
The recurrence for a cell is the best of three options:
dp[t][i - 1]: do nothing on dayi;dp[t - 1][i]: use one transaction fewer;maxDiff + prices[i - 1]: sell today the share bought on the best earlier day.
The value used for day j is dp[t - 1][j], not dp[t - 1][j - 1]. That also lets a sale and a purchase fall on the same day, which changes nothing: selling and buying again at one price is worth the same as holding on, so it never beats a legal plan or makes the answer too large.
The running best in action
For [3, 2, 6, 5, 0, 3] and t = 1, row 0 is all zeros, so the candidates are just the negative prices. After days 1 to 6, maxDiff holds -3, -2, -2, -2, 0 and 0. On day 3 (price 6) the sale option is -2 + 6 = 4, the profit of buying at 2. On day 6 (price 3) it is 0 + 3 = 3, which does not beat the 4 already in dp[1][5]. Row 1 ends with 4, and the same pass for t = 2 reaches 7 using row 1's values.
Step by step
- Store
prices.countinn. - Create the table as a
var:k + 1rows ofn + 1zeros. - Loop
tover1...k, one row per allowed number of transactions. - Declare
maxDiffinside that loop, set toInt.min. Each row starts fresh, since it refers to a differentt - 1row. The starting value must be as low as possible, because no day has been seen yet and the first candidate must replace it. - Loop
iover1...n, after the declaration ofmaxDiff. - Compute
dp[t][i]as the best of the three options, using two nestedmaxcalls. - Update
maxDiffwithdp[t - 1][i] - prices[i - 1]after computingdp[t][i]. A share bought on dayican be sold from dayi + 1, so today's candidate should only affect later days. - Return
dp[k][n].
The solution in Swift
class Solution {
func maxProfit(_ prices: [Int], _ k: Int) -> Int {
let n = prices.count
var dp = Array(repeating: Array(repeating: 0, count: n + 1), count: k + 1)
for t in 1...k {
var maxDiff = Int.min
for i in 1...n {
dp[t][i] = max(max(dp[t][i - 1], dp[t - 1][i]), maxDiff + prices[i - 1])
maxDiff = max(maxDiff, dp[t - 1][i] - prices[i - 1])
}
}
return dp[k][n]
}
}
Swift details worth knowing:
Int.minas "minus infinity". It is the smallest 64-bit integer. Adding to it can overflow, and Swift traps on overflow instead of wrapping. On day 1 the code computesInt.min + prices[0]. This is safe because prices are not negative, so the result only moves up. A negative price would crash the program at that line.- Type inference. The table has no annotation. Swift infers
[[Int]]from the literal0, and the rows are independent copies. - Nested
max. The globalmaxaccepts two arguments here, so three values need two calls. Swift'smaxcan take more arguments, but the nested form reads as clearly. - Ranges.
1...kand1...nare invalid ranges whenkis 0 or the price list is empty, which stops the program. The method assumesk >= 1and at least one price.
Complexity
Time: O(k * n). Each of the k * n cells is computed from a constant number of values.
Space: O(k * n). Row t only reads row t - 1, so two rows would be enough, reducing the space to O(n).
Edge cases and common mistakes
- Updating
maxDiffbefore computing the cell. It would still give correct answers, because buying and selling on the same day gains nothing, but the lesson updates it afterwards so the order matches the reasoning: buy first, sell on a later day. - Declaring
maxDiffoutside thetloop. The value from the previous row would leak into the next one and give wrong profits. - Starting
maxDiffat 0. It would pretend that a free share is available before day 1, and the method would return profits that are too large. For[5, 4]withk = 1it would return 5 instead of 0. - Falling prices. For
[5, 4, 3]the answer is 0. - Large
k. For[3, 2, 6, 5, 0, 3]andk = 5the answer remains 7: transactions that are not worth making are simply not made.
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 = [5, 4, 3],k = 2gives0.prices = [1],k = 1gives0.
