Best Time to Buy and Sell Stock IV

Another awesome problem on LeetCode deals with buying and selling stock. You are given a list of prices, are allowed to only open long positions and you must close one before opening a new one. This would be trivial (buy on low, sell on high), but you’re limited to a total of k buy/sell transaction pairs. You need to return the maximum profit.

At first I thought it was a dynamic programming problem. Quick peek at the tags confirmed that suspicion. I quickly realized that subproblems require to determine the maximum profit for d days, starting with 2 (can’t make a profit on one day because only one price per day is given). Moreover, it is quite obvious that we have to determine maximum profits for limited numbers of transactions in range 0..k. This requires only k memory because you only need the profits for the previous day to compute the tomorrow profits. You need to consider, though, that you may have left your position open, so some potential profit may exist. In this case you also have to record the opening price.

In the end it looked like this:

Not very elegant, but pretty straightforward. profitClosed[j] is the maximum profit that may be made by today with j buys/sells, while leaving no open position. profitOpen[j] is the same thing, but with open position and openPrice[j] denotes the best buying price so far, so we can instantly gain profitOpen[j] + current price − openPrice[j] by selling today. And that’s what we do, but only if the resulting profit is more than we could gain by performing less transaction. When we do it, the number of elements in the profitClosed array becomes greater than the number of elements in profitOpen, so we immediately open a new position on the next loop.

Then we update our profits in the inner loop. We re-close an open position if we can get a better profit and we reopen if we can get a better profit plus potential profit! That is important because that’s what an open position is about: if we can instantly get that much profit, it would be a waste to reopen at the current price even if we can get a better profit today, it will still bite us in the future.

This solution runs from 4 to 6 ms depending on the weather on Mars and the number of holes in the cheese. For example, replacing > profitClosed[lClosed] with > 0  in the pre-loop close-another-position condition speeds it up (branch prediction?) even though we open not very profitable positions.

There are much better solutions using the same idea. This one is particularly awesome, as it does both loops in just four lines.

However, I didn’t particularly like the DP idea here. It felt like this problem should have a better solution, so I kept on digging. After seeing this one, I decided to do the same thing in Java:

Not terribly concise, but pretty straightforward. The idea is that we calculate the profit that we’ll lose if we do nothing on a particular day, thus reducing the number of transactions. Then we keep on throwing away those days starting with those that give the least profit. Obviously throwing away days on monotonous intervals won’t affect the profit at all, so we don’t even add those to begin with. We are only interested in “peaks” and “valleys” (plus possibly the first and the last days).

Maybe replacing indices arrays with a linked list was a bad idea. It’s definitely worth to try arrays instead. As it is, it runs in 20 ms. Not so terribly efficient. But I don’t think switching to array will improve it that much because the main slowdown here is the tree. Even though I only add peak/valley days and do it only if transaction reduction is needed, it is still a pretty slow thing. And it still felt like not the totally right thing.

Then I saw this solution based on another one. And I must admin, it really took me a while to figure these out. Especially loop invariants. So I hereby present my own implementation of the same ideas that runs in 3 ms \mathcal{O}(n) (if we assume quickselect is linear, which is a fair assumption since randomization provides a very high average case probability).

And here comes the explanation.

stocks

Consider this price chart. Let’s consider only closing prices (80 for the first day, 70 for the 2nd, 75 for the 3rd and so on). For a “bullish” day (green) the closing price is the top of the candle, for a “bearish” one it’s the bottom. If we were to aim for the maximum profit, we’d perform the following transactions:

  1. Days 2–6, prices 70–100, profit 30.
  2. Days 8–11, prices 50–80, profit 30.
  3. Days 13–17, prices 20–60, profit 40.
  4. Days 19–21, prices 40–50, profit 10.
  5. Days 23–27, prices 30–70, profit 40.
  6. Days 29–31, prices 10–100, profit 90.

The total profit is 30+30+40+10+40+90=240.

Now, we are limited to some number of transactions. If that’s only one, then the best we can get is the last transaction, that is, 90. If two, then the best is to buy on the 13th day, sell on the 27nd (profit 50), buy on the 29th and finally sell on the 31st for the total profit of 140. Note that the first transaction is not even among the list of transactions we’d perform if we weren’t limited. That is because the first three transactions (green runs on the chart) are best united into a single one. So we need to figure out which transactions to unite.

Consider the following problem. For given intervals [v1, p1], [v2, p2], v1 < p2, v2 < p2, where “v” stands for a valley and “p” for a peak, what are the possible relationships between them? There are six:

  1. They don’t overlap, and p1 ≤ v2. For example, days 13–15 and 15–17 with prices [20,40], [40,60].
  2. They don’t overlap, and v1 ≥ p2. For example, days 2–6 and 13–17 with prices [70,100], [20,60].
  3. They do overlap, and v2 < p1. For example, days 13–17 and 23–27 with prices [20,60], [30,70].
  4. They overlap, and v1 < p2. For example, days 2–6 and 8–11 with prices [70,100], [50,80].
  5. The second interval is fully included in the first one. For example, days 13–17 and 19–21 with prices [20,60], [40, 50].
  6. The first interval is fully included in the second one. For example, days 23–27 and 29–31 with prices [30,70], [10,100].

I’m not totally rigorous here about the strictly-less/less-than-or-equal thing. It doesn’t matter, though, because corner cases when something is equal to something else may be handled as either—they are kind of “at the border” between the two and belong to both sets. For example, if two transactions have exactly the same price range, then it doesn’t really matter whether you think of the second one included in the first one or vice versa. Or you may even want to consider them to be overlapping.

Now we need to ask ourselves a question: if we have two transactions and are allowed to make only one, how to get the maximum profit? Let’s consider all six cases.

Two transactions: both giving 20, both on the increasing interval

Case 1: transactions (1) and (2) are combined into (3)

The first case is not really possible for adjacent transactions if we only consider “peak—valley” transactions to begin with (the end of the second transaction is not really a peak, and the beginning of the second one is not a valley). Indeed, if two intervals form a monotonous non-decreasing sequence, then why bother splitting them in two intervals at all? However, for transactions far apart, this case is still possible (although not in our example). Anyway, in this case the answer is quite obvious: just combine two transactions into a single one, buying on for v1, selling for p2.

Case 2: one transaction gives 30, another 40, but it's way below the first one, so we can't combine them

Case 2: between transactions (1) and (2) we pick (2) because it’s more profitable

The second case is also obvious: just pick up the most profitable one. We can’t unite them because the starting price of the first one is greater than the selling price of the second one. If you buy on the 2nd day and sell on 17th, you’ll have 10 loss instead of any profit.

Two transactions overlap and the best profit is from the start of the first one to the very end of the second one

Case 3: two overlapping transactions (1) and (2) are transformed into one long transaction (3) and an imaginary short transaction (4)

The third case is the most tricky one! Since the lowest price is v1, and the highest price is p2, then the best is to combine them into a single transaction. This sounds like it increases the transaction count tremendously (as we have to consider all possible combinations), but in fact it doesn’t. We do a really amazing trick here: instead of considering them as two separate transactions to begin with, we instead think of them as one “long” transaction (buying at v1, selling at p2) and one “short” transaction (selling at p1 and buying later at v2), even though short transactions aren’t technically allowed by this problem! This works because we pick transactions starting with the ones giving us the most profit. In this case, the long one is guaranteed to give us more profit than the short one, so we’ll either pick the long one (without violating anything) or pick both. And since both transactions give us exactly the same profit as two long transactions we had to begin with (p1-v1+p2-v2=p2-v1+p1-v2), then it’d appear in the net result as if we performed two separate long transactions.

Two transactions overlap, but the combined one gives less profit

Case 4: between transactions (1) and (2) we choose the most profitable (in this case any of them) because the combined transaction (3) is the least profitable

The fourth case is trivial: since the combined transaction is the least profitable, we just pick the most profitable one of the two. In our example they are equally profitable, though.

Two transactions, the second one has higher valley and lower peak

Case 5: the second transaction is included in the first, so the first one gives the best profit we can get

The fifth case is even more boring: the first transaction has both the lowest price and the highest price, so we just pick the first one.

Two transactions, the second one has the lowest and the highest prices

Case 6: the second transaction gives the most profit

The sixth case is the mirror image of the fifth one. Just pick the second transaction.

So we have one case when we should combine transactions unconditionally, two cases when we should choose the most profitable of the two, two cases when the most profitable one is obvious and one tricky case when we transform two long transactions into one long and one imaginary short one. Now to the algorithm.

The algorithm preserves the following invariant. When an outer loop iteration finishes, the valleys/peaks stack contains transactions that are related according to case 5 above, with the latest transaction on the top. The invariant is obviously true at the beginning since the stack is empty, and any proposition is true for the elements of an empty set (all humans that have visited other galaxies have green ears—there are none at the moment of writing, so I’m not wrong in saying that “all” (zero) of them have green ears).

The invariant is preserved by these two loops:

The first loop just pops transactions with v1 > v2, which corresponds to cases 2, 4 and 6. In all these cases we don’t combine transactions, so it’s fine to just pop them and consider separately. The termination condition guarantees that v1 ≤ v2 at the end of that loop, assuming there are any elements left in the stack.

The second loop handles the tricky case 3. We pop a transaction, then generate a “short” transaction and put it into the profits array. Then we set the current valley to the one popped from the stack, so the current transaction now corresponds to the long one. Then we continue the loop because it may or may not be possible to combine it with the previous one and so on. Note that the termination condition guarantees that p1 > p2 at the end of the loop, assuming there are any elements left. Assuming the invariant held true at the start of the outer loop, popping some elements could not have increased the valley at the top of the stack because it may only decrease as we go deeper.

Note that we don’t consider case 1 separately. Instead, we treat it as a special subcase of case 3 where the “short” transaction gives us negative profit. Since we’re going to pick only the highest profits anyway, this is fine. One may think that it may have negative impact on the total profit in the case where k is high enough to allow all transactions to complete, but in fact it may not. This is because two adjacent transactions can’t form case 1 anyway, remember? So when we have transactions like this, it means that they are separated by some transactions in the middle. And if we’re going to pick every profitable transaction, then we can’t really combine those two because we aren’t allowed to engage in multiple transactions. So this negative profit corresponds to the profit loss caused by the fact that we need to sell first in order to buy again.

Lastly, since case 5 corresponds to the items in the stack, we pick top k profits using randomized quickselect and sum them up.

One last note before we get to the example: the loop may generate one false peak/valley pair at the end of the input array if the prices list ends with a valley. This corresponds to a zero-length transaction giving zero profit, so instead of checking for this corner case we can allocate one more element in the profits array to hold this zero. It won’t affect the result in any way.

Now let’s see how the algorithm works on our example. Our valleys/peaks are: 70–100, 50–80, 20–60, 40–50, 30–70, 10–100.

Step 1 (70–100). The stack is empty, so the inner loops don’t execute. The stack becomes (bottom-to-top)

Step 2 (50–80). The first loop pops the transaction because 70 > 50 (case 4). The stack becomes empty, therefore the second loop doesn’t execute. The next transaction is pushed into the stack.

Step 3 (20–60). The first loop pops because 50 > 20 (case 4). The rest is just like the previous step.

Step 4 (40–50). The first loop doesn’t work because 20 < 40. The second loop doesn’t work either because 60 > 50. Case 5.

Step 5 (30–70). The first loop pops only [40,50] because 40 > 30 (case 6), but 20 < 30. The second loop then transforms [20,60] and [30,70] into [60,30] (added to the profits) and [20,70] (becomes the current transaction). This is case 3.

Step 6 (10–100). The first loop pops because 20 > 10 (case 6). The second loop doesn’t work because the stack is now empty. The last transaction is pushed into the stack.

Lastly, we pop the stack and we now have

A total of six transactions! Now for the different values of k we have:

  1. Just pick up the last transaction.
  2. Pick up 50 and 90, where 50 corresponds to 20–70 produced on the 5th step (buy on the 13th, sell on the 27th).
  3. Pick up 50, 90 and any of the 30s, where 30s can be one of the first two transactions or the imaginary transaction that splits our 50 into 20–60 (days 13–17) and 30–70 (days 23-27), which gives 40+40 = 50+30.
  4. Pick up 50, 90 and any two of the 30s.
  5. Pick up 50, 90 and all of the 30s (meaning 50+30 now definitely means two real transactions 40+40).
  6. Pick all of them (the trivial unrestricted case).

Isn’t this awesome?

Leave a Reply