Problem overview
You get an array prices where prices[i] is a stock's price on day i, and a limit k on the number of transactions. A transaction is one buy followed by one sell. You can't hold two positions at once, so you must sell before you buy again. MaxProfit returns the largest total profit you can make.
For prices = [3, 2, 6, 5, 0, 3] and k = 2, the best plan is to buy at 2 and sell at 6 (profit 4), then buy at 0 and sell at 3 (profit 3). The answer is 7. With prices = [2, 4, 1] and k = 2, only one trade is worth making: buy at 2, sell at 4, for a profit of 2.
Approach: turn the chart into valleys and peaks
The usual way to solve this problem is dynamic programming over days and transaction counts. This lesson uses a greedy idea that runs in O(n log n) because of one sort.
Any profitable trade buys at the bottom of a dip and sells at the top of the rise that follows. So the first job is to cut the price chart into (bottom, top) pairs, one per dip-then-rise. For [3, 2, 6, 5, 0, 3] these pairs are (2, 6) and (0, 3).
If the pairs were all independent, you would sort their profits and take the best k. They aren't always independent. Take [1, 5, 2, 6], whose pairs are (1, 5) and (2, 6). With one transaction the best choice is to buy at 1 and sell at 6, which spans both pairs and earns 5. With two transactions the best choice is the two pairs themselves, which earn 4 and 4, for a total of 8.
The key observation is that merging two pairs (b1, t1) and (b2, t2) into (b1, t2) needs a second candidate to stay lossless. The two separate trades earn (t1 - b1) + (t2 - b2), which equals (t2 - b1) + (t1 - b2). So the merged trade, plus the "give-back" trade t1 - b2, represents the same total. If you may only pick one, you pick the bigger merged trade. If you may pick two, you pick both and recover the original total.
A stack does this merging in one pass over the pairs. When all the candidates are settled, sort them in descending order and add up the first k.
Step by step
Extracting the pairs: findBottomTopPrices
- Declare the helper above
MaxProfit. It takes the prices and returns aList<int[]>, where a two-element array stands in for a pair. - Keep
n, the length, andi, the day being examined, and create the list that collects the pairs. - Loop while
i < n, so every day is consumed by exactly one pair. - Start
bottomatiand walk it right while the price doesn't increase. It stops on the cheapest day of the dip. The bounds checkbottom + 1 < ncomes first so the next price is never read past the end. - Start
topatbottomand walk it right while the price doesn't decrease. It stops on the highest day of the rise, again with the bounds check first. - Add the two prices as a new two-element array, then continue from
top + 1. - Return the list, and in
MaxProfitstore it inbottomTopPrices.
Settling the pairs: computeProfits
- Declare
computeProfitsabove the first helper. It takes the pairs and returns aList<int>of independent candidate profits. - Create an empty
Stack<int[]>for pairs that are not decided yet, and the listprofits. - Loop over the pairs with
foreach. Copy the two values into local variablesbottomandtop, becausebottomwill change during a merge. - First inner loop: while the stack is non-empty and the current
bottomis lower than the stacked pair's bottom, the stacked pair can never be extended, because any later merge prefers the deeper bottom. Add its profit (top minus bottom) and pop it. - Second inner loop: while the stack is non-empty and the current
topis at least the stacked pair's top, the two pairs merge. Add the give-back profit, the stacked top minus the currentbottom. Then take over the stacked pair's lower bottom and pop it. - Push
(bottom, top), since a later pair may still merge with it. - After the loop, pop what remains and add each leftover pair's own profit.
Choosing the best k: MaxProfit
- Call
computeProfitswith the pairs. - Reduce
kwithMath.Minso it never exceeds the number of candidates. - Sort the profits in descending order, add the first
kintoresultand return it.
The solution in C#
class Solution {
List<int> computeProfits(List<int[]> bottomTopPrices) {
Stack<int[]> stack = new Stack<int[]>();
List<int> profits = new List<int>();
foreach (int[] bottomTop in bottomTopPrices) {
int bottom = bottomTop[0];
int top = bottomTop[1];
while (stack.Count > 0 && bottom < stack.Peek()[0]) {
profits.Add(stack.Peek()[1] - stack.Peek()[0]);
stack.Pop();
}
while (stack.Count > 0 && top >= stack.Peek()[1]) {
profits.Add(stack.Peek()[1] - bottom);
bottom = stack.Peek()[0];
stack.Pop();
}
stack.Push(new int[]{bottom, top});
}
while (stack.Count > 0) {
profits.Add(stack.Peek()[1] - stack.Peek()[0]);
stack.Pop();
}
return profits;
}
List<int[]> findBottomTopPrices(int[] prices) {
int n = prices.Length, i = 0;
List<int[]> bottomTopPrices = new List<int[]>();
while (i < n) {
int bottom = i;
while (bottom + 1 < n && prices[bottom] >= prices[bottom + 1]) {
++bottom;
}
int top = bottom;
while (top + 1 < n && prices[top] <= prices[top + 1]) {
++top;
}
bottomTopPrices.Add(new int[]{prices[bottom], prices[top]});
i = top + 1;
}
return bottomTopPrices;
}
public int MaxProfit(int[] prices, int k) {
List<int[]> bottomTopPrices = findBottomTopPrices(prices);
List<int> profits = computeProfits(bottomTopPrices);
k = Math.Min(k, profits.Count);
profits.Sort((a, b) => b - a);
int result = 0;
for (int i = 0; i < k; ++i) {
result += profits[i];
}
return result;
}
};
On [1, 5, 2, 6], findBottomTopPrices returns (1, 5) and (2, 6). When the second pair arrives, its top 6 is at least the stacked top 5, so computeProfits adds the give-back profit 5 - 2 = 3 and pushes the merged pair (1, 6). At the end it adds 6 - 1 = 5. The candidates are [3, 5]: with k = 1 the answer is 5, and with k = 2 it is 8.
The C# details worth noting:
- Collections need
using System.Collections.Generic;forList<T>andStack<T>. Arrays have.Length, while lists and stacks have.Count. Peek()versusPop().Peek()reads the top of the stack, andPop()removes it. Calling either on an empty stack throwsInvalidOperationException, which is why every loop testsstack.Count > 0first.&&skips the right side when the left side is false.- Sorting with a lambda.
profits.Sort((a, b) => b - a)orders larger values first, because a positive result meansagoes afterb. Subtracting is safe here since the profits are small. For arbitrary ints,b.CompareTo(a)avoids overflow. - The loop variable of
foreachis read-only. You can't assign to the pair, which is why the code copies its values intobottomandtop. - Parameters are local copies. Assigning
k = Math.Min(k, profits.Count)changes onlyMaxProfit's ownk.
Complexity
Time: O(n log n). Extracting the pairs is one pass, since i only moves forward. Each pair is pushed and popped at most once, so computeProfits is O(n). Sorting the candidates takes O(n log n) in the worst case. A selection technique for the k largest values would bring the whole thing down to O(n).
Space: O(n). The pair list, the stack and the profit list each hold at most about n / 2 entries.
Edge cases and common mistakes
- Empty input or falling prices. An empty array produces no pairs and the answer is 0. For
[5, 4, 3]the only pair is(3, 3), which earns 0. - Large k. With
kbigger than the number of candidates, theMath.Minline stops the final loop from reading past the end ofprofits. - Flat prices. Because the walks use
>=and<=, equal neighbours extend a dip or a rise instead of splitting it. - Swapping the loop conditions. Writing
bottom + 1 < nafter the price comparison reads past the end of the array and throwsIndexOutOfRangeException. - Dropping the give-back profit. Without it, merged pairs lose profit when
kallows both trades. - Taking profits without sorting. The candidates aren't in order of size, so the first
kare not the bestk.
Testing
prices = [2, 4, 1],k = 2gives2.prices = [3, 2, 6, 5, 0, 3],k = 2gives7, and withk = 1gives4.prices = [1, 5, 2, 6],k = 1gives5, and withk = 2gives8.prices = [1, 2, 3, 4, 5],k = 3gives4.prices = [5, 4, 3],k = 2gives0.