Vector thinking for Max Profit | iabdb
Occasionally I am lucky enough to run into a problem that doesn’t already have many vector solutions, so I can demonstrate how vector thinking can allow you to find an elegant solution. To build up to my insight let’s solve 2 easy variations and then we can get to the two more interesting puzzles.<br>The problem in question is called Best Time to Buy and Sell or more popularly simply Max Profit.<br>The theme is always the same you are given an ordered list of positive numbers that represent the evolution of the price of the security. You must find the maximum profit you could have made given this price series. You can only hold 1 unit at a time and you can not short, which means you must buy before you can sell (you can only profit from the price evolving upward).<br>The simplest and most well know variation is the 1 transaction problem (leetcode problem 121): you can only buy and sell at most 1 time what is the max profit that can be earned from the following series:<br>example series:<br>3 2 5 1 3 2 4 9 5 12 3 5<br>The key insight into this problem is that we are looking for the largest difference between the current element and the smallest element we have seen.<br>To motivate this insight, let’s look at ever larger versions of this problem starting with just one price to detect the pattern.<br>3 -> 0<br>Given just one price we can only buy and sell on the same day, so effectively max profit is 0<br>3 2 -> 0<br>Given these two points we can still only earn 0, since we must sell after we buy.<br>3 2 5 -> 3<br>Now that we have a higher number after a lower number we can plainly see that of the two options buy at 3 or buy at 2, buy at 2 and sell at 5 is better.<br>3 2 5 1 -> 3<br>The answer is still 3, since we can’t sell higher than 5, and even if we bought at 1 at the end there are no days left to sell<br>3 2 5 1 3 -> 3<br>We still do best by buying at 2 and selling at 5, buying at 1 and selling at 3 only earns 2.<br>3 2 5 1 3 2 -> 3<br>Plainly the 2 at the end doesn’t improve<br>3 2 5 1 3 2 4 -> 3<br>We can now either buy at 2 and sell at 5 or buy at 1 and sell at 4, but our max profit is still 3.<br>3 2 5 1 3 2 4 9 -> 8<br>Finally, the max profit changes! We can now buy at 1 and sell at 9. As new elements are added the new reward will be a function of the lowest element seen thus far.<br>We then get our solution:<br>{max x-mins x} 3 2 5 1 3 2 4 9 5 12 3 5<br>11, where we buy at 1 and sell at 12.<br>Or in python we could say something like:
import itertools<br>from operator import sub<br>def max_profit(p):<br>return max(map(sub,p,itertools.accumulate(p,min)))
To unpack this a bit, mins returns the min element up to that point:<br>mins[3 2 5 1 3 2 4 9 5 12 3 5]<br>3 2 2 1 1 1 1 1 1 1 1 1<br>we can then do element-wise subtraction to see what the profit is from selling at each point<br>0 0 3 0 2 1 3 8 4 11 2 4<br>taking the running max we get the max profit so far,<br>0 0 3 3 3 3 3 8 8 11 11 11<br>we can see that this series is exactly the results that we got when we were looking at the max profit for the prefixes of the series.
Easy enough, let’s look at version 2 of this problem (leetcode 122):<br>unlimited number of transactions: We are now allowed to buy and sell as often as we like provided we never own more than 1 share of the stock and we still must sell after we bought. To make things easier we can assume that we can buy and sell on the same day, in practice this doesn’t matter as any day we do this we can consider that we did nothing.<br>Keeping the same price series as before:<br>3 2 5 1 3 2 4 9 5 12 3 5<br>We now notice that we should take advantage of every single time the price goes up. Again let’s look at a smaller example to get some intuition.<br>3 2 5 -> 3<br>Nothing fancy here, we buy at 2 and sell at 5, purchasing at 3 doesn’t improve our profit since selling at 2 would incur a loss.<br>3 2 5 1 3 -> 5<br>buy at 2 sell at 5, buy at 1 sell at 3<br>3 2 5 1 3 2 4 -> 7<br>just add one more purchase at 2 and sell at 4,<br>3 2 5 1 3 2 4 9 -> 12<br>Here it becomes interesting, we can look at two interpretations<br>buy at 2 sell at 5 (3),buy at 1 sell at 3 (2), buy 2 sell at 9 (7) for a total of 12<br>or we can say:<br>buy at 2 sell at 5 (3),buy at 1 sell at 3 (2), buy at 2 sell at 4 (2),buy at 4 sell at 9 (5) for a total of 12.<br>The two approaches are identical since addition commutes, it doesn’t matter how you get from 2 – 9 you will always earn 7.<br>Which means that we can simply add up the positive steps in the price series. That will be the maximum profit for an unlimited number of transactions:<br>Our code is simply:<br>{(x>0) wsum x:1 _ deltas x} 3 2 5 1 3 2 4 9 5 12 3 5<br>21<br>Deltas gives us the adjacent differences. We drop the first delta since we cannot sell before we have bought. If the delta is positive >0 we want to include it in our sum. Using (w)eighted(sum) we weight the >0 with a 1 and less then 0 or =0 are given a weight of 0.
Now that we covered the case with 1 transaction and unlimited transactions, we should feel confident that we can tackle 2 transactions. Lucky for us, that’s exactly version...