This is the trickiest problem I’ve seen so far on leetcode. Given that I’ve just done 25 problems this is not so convincing, but to me I really feel like writing something about this problem. I think this problem is different than many other problems in that it can hardly be classified. For example there are tons of problems that requires recursive backtracking and a bunch of related to graph searching, you can easily tell what problem is what if you have seen enough problems. But this problem is kind of ‘gotcha’ as it is not a string problem, not a list/tree problem, and cannot be classified to recursion (although it seems like but it is totally wrong direction to think). I can imagine if I come across this problem in an interview I would be dead.
I am not going to repeat the problem here, nor will I write any code. I want to describe the correct solution and how I went to the wrong way. First part asks about the max profit with exact one buy and one sell. At first sight probably everyone will think: ok let’s find the max value and min value, but then we realize that it won’t work because the min does not necessarily come before the max value. This is the most interesting feature in this problem series. Then I tried to think of all the possibilities and found out that we need to keep looking for minimum value and also looking for maximum value after the minimum, and compare the difference with that of the maximum and minimum pair we found before. This sound awkward but it naturally came to me when I first did it. Then I spent lots of effort on finding those maximum and minimum value and ended up with a TLE. Then I searched for the solution and the correct solution is about 2o lines of code. I felt like an idiot when I saw it. (I wonder if someone had the same feeling so I won’t be so sad) The fact is that it makes a trick and bypasses the effort to find a maximum point. The idea is that while you are progressing, only update the minimum point you come across, and check the current point against the minimum point to get profit (imagine you buy at minimum and sell at current point). This way you don’t need to know where the maximum point is. This is not straightforward but is magically true. It is based on the fact that the maximum profit you can make at current point depends on the minimum point appears before it. Moreover, not only you find the profit at a maximum point but every point. This property is also used in part III, but I doubt anyone will think of this when they’ve taken a different (maybe a dumb) path like me.
Part II asks for profit with no limitation on number of buys and sells, but every buy-sell pair happens after the previous pair finishes. The idea in part I does not apply here, because obviously you should sell when the trend is going down and buy at next minimum. So I went back to my previous thought of finding “minimum-maximum” pair. I just couldn’t resist it. But again there’s a much more elegant way to do this. The code is even shorter than the previous one. The idea is just compare the current point to the previous point, if it’s bigger than the previous one, add the difference to the total profit. This way you don’t miss any increasing pair. The maximum profit is nothing more than adding up these increasing pair altogether. I believe this hidden property is less ambiguous than the one in part I. It naturally capture every up-going trend. The take away from this part for me is to think small, think discretely. I don’t know if I explain this clear but in computer science some tricks are made possible due to the discrete property of the problem.
Ok, finally part III. With the knowledge obtained in part I. Hopefully you already find out that each one of the two buy-sell pairs must have the max profit solution in its session. For example, assume we found out the solution to get max profit then there must exist a point ‘i’ after the first sell and before the second buy (the extreme case is that the first sell happens just the same time with second buy, then ‘i’ would be just that point), then what we have done before ‘i’ had better achieved max profit, otherwise it will contradict to our assumption as we can improve the profit in that session and therefore the total profit, and same thing for the case after ‘i’. But I have to say it is still a little against our instinct. If you directly look at this problem, for example some typical thoughts I have are: ‘Should I find out the first/second high point or first/second low point’, ‘How to catch the first/second steepest slope’, ‘Apparently there are ‘n’ choices for each buy and sell, and the problem would be O(n^4) complexity, seriously?’… Anyway, assume we are on the right track now. For every possible point ‘i’, we apply solution from part I on both left and right side of ‘i’, and we get a max profit for each ‘i’, we pick the biggest one at last, sounds easy right? This is close as OJ rewarded me with a TLE. Think more carefully, solution for part I is O(n), here we add an outer loop so it becomes O(n^2). It is easy to find out we have done a lot of unnecessary scans. Probably we can memorize something when we are doing one scan. Here we need some dynamic programming. The key point is that the max profit before or after a point is fixed, and the only information we need to calculate is nothing more than the previous max profit, current min/high point, and the value of ‘i’ itself. All these information are available within one scan–we have one variable track the min/high point, and as we progress we can get the current max profit which becomes ‘previous max profit’ for the next point.
One more tricky thing: How to find the maximum profit after point ‘i’? Previously we scan from left to right, when we scan to ‘i’, we know the result of ‘i-1’, but we have no idea what will happen after ‘i’, unless we scan all the way to right end, but this break the rule of O(n). Here we need to think differently. If we know what will happen after ‘i+1’, then we know what will happen after ‘i’. This brings the idea to scan from right to left. To be honest this idea still sounds mysterious to me. It’s like travel from future to the past. I’d like to compare the difference in two scans. When scan from left to right, we view the min point as a potential buy point and look into future to find a sell point, but when we scan from right to left, we view the max point as sell point and look for buy point in the past. Why? The only explanation I can think is that there exists an order for ‘buy’ to happen before ‘sell’. To calculate things on the left, we can only assume a ‘buy’ already happened somewhere in the past, because we sell before ‘i’, the minimum point before ‘i’ is the only time we can buy. Same logic, if we want to calculate things on the right, then there must be a ‘sell’ in the future, because we buy after ‘i’, the maximum point after ‘i’ is the only point we can sell. It feels like someone knows what he did in the future and is looking for an answer in the past. Greetings, time traveller.