Problem overview
The method maxProfit receives prices, an Array[Int] with one stock price per day, and k, the maximum number of transactions. A transaction is one buy followed by one later sell, and you must sell before you buy again. The method returns the largest total profit.
For [3, 2, 6, 5, 0, 3] with k = 2 the answer is 7: buy at 2 and sell at 6 for a profit of 4, then buy at 0 and sell at 3 for 3. For [2, 4, 1] with k = 2 the answer is 2, because only one profitable trade exists.
Approach: turn the chart into candidate trades
A table that tracks the best profit for every day and every number of transactions solves the problem with dynamic programming, but it costs O(n * k). This lesson uses a different idea that needs no table.
Every useful trade buys at the bottom of a dip and sells at the top of the following rise. So first compress the chart into its (bottom, top) pairs, one for each dip followed by a rise. For [3, 2, 6, 5, 0, 3] these are (2, 6) and (0, 3).
The pairs are not always independent. Take [1, 5, 2, 6], which gives (1, 5) and (2, 6). With one transaction the best choice is to buy at 1 and sell at 6, a profit of 5, which spans both pairs. With two transactions the two pairs separately earn 4 + 4 = 8.
The key identity: two trades (b1, t1) and (b2, t2) with b1 <= b2 and t1 <= t2 earn (t1 - b1) + (t2 - b2), which equals (t2 - b1) + (t1 - b2). So a stack merges them into the wider trade (b1, t2) and records the leftover t1 - b2 as a separate candidate profit. In the example, the merged trade is worth 5 and the leftover is 5 - 2 = 3, which gives the candidates 5 and 3.
Once every candidate profit is known, the answer is the sum of the k largest ones, or all of them if there are fewer than k.
Step by step
findBottomTopPricescollects the pairs. It keeps a day indexiand a buffer of pairs, and runs while days remain.- Find the bottom. Starting at
i, movebottomforward while the price doesn't increase. Checkbottom + 1 < nfirst, so the next price is never read past the end of the array. - Find the top. Starting at the bottom, move
topforward while the price doesn't decrease, with the same bounds check first. - Record the pair of prices, then continue from
top + 1. Convert the buffer withtoListat the end. computeProfitsturns pairs into independent profits. It uses a stack of pairs whose best partner isn't decided yet, and a buffer of finished profits.- For each pair, set
bottomandtop.bottomis avarbecause merging can lower it. - Settle deeper stacked pairs. While the stack isn't empty and the current
bottomis lower than the stacked pair's bottom, that stacked pair can never be merged with later pairs, so its profit is final. Add it and pop it. The emptiness check comes first so the top is only read when it exists. - Merge with lower, lower-topped pairs. While the stack isn't empty and
topis at least the stacked pair's top, add the leftoverstack.top(1) - bottomto the profits, take the stacked pair's lower bottom, and pop it. - Push the current pair with its possibly lowered bottom. Later pairs may merge with it.
- Flush the stack at the end: every pair still there adds its own profit.
- Pick the best. In
maxProfit, compute the pairs, then the profits, and setlimitto the smaller ofkand the number of profits. Sort the profits in decreasing order and add the firstlimitvalues.
The solution in Scala
class Solution {
def computeProfits(bottomTopPrices: List[Array[Int]]): List[Int] = {
val stack = scala.collection.mutable.Stack[Array[Int]]()
val profits = scala.collection.mutable.ArrayBuffer[Int]()
for (bottomTop <- bottomTopPrices) {
var bottom = bottomTop(0)
val top = bottomTop(1)
while (stack.nonEmpty && bottom < stack.top(0)) {
profits += stack.top(1) - stack.top(0)
stack.pop()
}
while (stack.nonEmpty && top >= stack.top(1)) {
profits += stack.top(1) - bottom
bottom = stack.top(0)
stack.pop()
}
stack.push(Array(bottom, top))
}
while (stack.nonEmpty) {
profits += stack.top(1) - stack.top(0)
stack.pop()
}
return profits.toList
}
def findBottomTopPrices(prices: Array[Int]): List[Array[Int]] = {
val n = prices.length; var i = 0
val bottomTopPrices = scala.collection.mutable.ArrayBuffer[Array[Int]]()
while (i < n) {
var bottom = i
while (bottom + 1 < n && prices(bottom) >= prices(bottom + 1)) {
bottom += 1
}
var top = bottom
while (top + 1 < n && prices(top) <= prices(top + 1)) {
top += 1
}
bottomTopPrices += Array(prices(bottom), prices(top))
i = top + 1
}
return bottomTopPrices.toList
}
def maxProfit(prices: Array[Int], k: Int): Int = {
val bottomTopPrices = findBottomTopPrices(prices)
val profits = computeProfits(bottomTopPrices)
val limit = math.min(k, profits.length)
val sorted = profits.sortWith(_ > _)
var result = 0
for (i <- 0 until limit) {
result += sorted(i)
}
return result
}
}
The Scala details worth a closer look:
- Immutable and mutable collections.
Listis immutable, so the helpers collect into a mutableArrayBufferwith+=and convert withtoListat the end.mutable.Stackofferspush,top,pop()andnonEmpty. - Semicolons.
val n = prices.length; var i = 0puts two declarations on one line. Usually Scala needs no semicolons. &&short-circuits. Inbottom + 1 < n && prices(bottom) ...the right side is skipped when the left side is false, which keeps the index in bounds.sortWith(_ > _). The underscores stand for the two arguments of the comparison, so the call sorts largest first. It returns a new list and leavesprofitsunchanged.- Parameters can't be reassigned, so
limitis a newval.
Complexity
Time: O(n log n). Extracting the pairs and running the stack are both O(n): every day is visited once, and each pair is pushed and popped at most once. Sorting the profits costs O(m log m), where m <= n is the number of candidates. Selecting the k largest without a full sort brings the total to O(n).
Space: O(n). The pairs, the stack and the profits each hold at most about n entries.
Edge cases and common mistakes
- Falling or flat prices.
[5, 4, 3]produces the single pair(3, 3), a profit of 0. The method returns 0 for it, and for[3, 3, 3]too. - Empty prices. The loop never runs and the method returns 0.
k = 0.limitis 0, nothing is added, and the result is 0.- Large
k. Withk = 10on[3, 2, 6, 5, 0, 3],limitbecomes 2 and the answer stays 7. - One transaction.
[1, 5, 2, 6]withk = 1returns 5, the merged trade. Withk = 2it returns 8. - Reading past the end. Putting
prices(bottom + 1)before thebottom + 1 < ncheck throws anArrayIndexOutOfBoundsException. - Popping before reading. Read the stacked pair's values before
pop(), because the pair is gone afterwards.
Testing
[2, 4, 1],k = 2gives2.[3, 2, 6, 5, 0, 3],k = 2gives7.[3, 2, 6, 5, 0, 3],k = 1gives4.[1, 5, 2, 6],k = 1gives5, and withk = 2gives8.[],k = 3gives0.
