Problem overview
The method maxProfit(_ prices: [Int], _ k: Int) receives the price of a stock on each day and a limit k on the number of transactions. A transaction is one buy followed by one later sell. You may hold at most one share at a time, so you must sell before you buy again. The method returns the largest total profit.
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 the answer is 7: buy at 2 and sell at 6 for 4, then buy at 0 and sell at 3 for 3. If no profitable trade exists, the best choice is to make none and the profit is 0.
Approach: best profit by transactions and days
The number of ways to choose buy and sell days grows very quickly, so the lesson uses a table. Let dp[t][i] be the best profit using at most t transactions during the first i days. Row 0 (no transactions) and column 0 (no days) are 0.
To compute dp[t][i], consider what happens on day i:
- No sale on day
i. The best profit is whatever was possible in the firsti - 1days withttransactions,dp[t][i - 1]. Using fewer transactions is also allowed, sodp[t - 1][i]is a valid lower bound too. - A sale on day
i. The share was bought on some earlier dayj. That transaction earnsprices[i - 1] - prices[j - 1], and before dayjthere were at mostt - 1other transactions, worth at mostdp[t - 1][j - 1].
Take the best of all of these. The answer is dp[k][n]. For the second example, the table with k = 2 looks like this, with columns for days 0 to 6:
t=0: 0 0 0 0 0 0 0
t=1: 0 0 0 4 4 4 4
t=2: 0 0 0 4 4 4 7
The last cell, 7, is the answer. The cost of this approach is the inner loop over j, which makes the time O(k * n^2). The follow-up lesson on this problem removes that loop.
One cell in detail
Take dp[2][6] for the second example. The first max gives 4, from dp[2][5]. Then the loop over j tries each buy day. Buying on day 5 (price 0) and selling on day 6 (price 3) has profit = 3. The value before day 5 with at most one transaction is dp[1][4] = 4, so the candidate is 4 + 3 = 7. Buying on day 2 instead gives profit = 1 and dp[1][1] = 0, so the candidate is only 1. The maximum is 7.
Step by step
- Store
prices.countinn. It is used many times. - Create the table as a
var:k + 1rows ofn + 1zeros. - Loop
tover1...k. Row 0 stays 0. - Loop
iover1...n. Column 0 stays 0. - Start from what is already known:
dp[t][i]is the larger ofdp[t][i - 1]anddp[t - 1][i]. - Try every buy day
jfrom 1 up to, but not including,i, with1..<i. - Compute the profit of buying on day
jand selling on dayi. Days start at 1 but the array starts at index 0, so daydhas the priceprices[d - 1]. - Keep the larger value. If the profit plus
dp[t - 1][j - 1]beats the currentdp[t][i], update it. Usemax. - Return
dp[k][n].
The solution in Swift
class Solution {
func maxProfit(_ prices: [Int], _ k: Int) -> Int {
let n = prices.count
var dp = [[Int]](repeating: [Int](repeating: 0, count: n + 1), count: k + 1)
for t in 1...k {
for i in 1...n {
dp[t][i] = max(dp[t][i - 1], dp[t - 1][i])
for j in 1..<i {
let profit = prices[i - 1] - prices[j - 1]
dp[t][i] = max(dp[t][i], dp[t - 1][j - 1] + profit)
}
}
}
return dp[k][n]
}
}
Swift details worth knowing:
- Empty and invalid ranges. For
i = 1the range1..<1is empty and the inner loop does nothing, which is correct: no earlier day exists. A closed range such as1...kwithk = 0, or1...nwith an empty price list, has a lower bound above its upper bound, so the program stops with a run-time error. The method assumesk >= 1and at least one price. - Value-type rows. The nested
repeating:count:builds independent rows, sodp[t][i] = ...changes only one cell. maxwith two arguments. The globalmaxreturns the larger of its arguments. The code reads and writes the same celldp[t][i]through it, which is safe.- Negative profit.
profitcan be negative when the price falls. The sum withdp[t - 1][j - 1]is then below the value from the firstmax, so a losing trade never wins.
Complexity
Time: O(k * n^2). There are k * n cells, and each runs a loop over up to n - 1 buy days.
Space: O(k * n). The table has (k + 1) * (n + 1) integers.
Edge cases and common mistakes
- Falling prices. For
[5, 4, 3]every trade loses money, and the answer is 0. - A single day. With
[1]no sale is possible, and the answer is 0. klarger than needed. With[3, 2, 6, 5, 0, 3]andk = 5, the answer is still 7: extra transactions are allowed but unnecessary, because the limit is "at most".- One transaction. With
k = 1the same prices give 4, buying at 2 and selling at 6. - Day numbers against array indices. Using
prices[i]instead ofprices[i - 1]reads past the end on the last day. - Using the wrong previous profit. Adding
dp[t - 1][i - 1]ordp[t][j - 1]instead ofdp[t - 1][j - 1]could let two transactions overlap or exceed the limit.
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.
