Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
(Java Code on github at the bottom of the post. )
My thoughts and solutions:
Well in fact there are 3 questions in the series. I was actually working on the 3rd one because the OJ randomly picked it for me. I couldn’t figure it out but it helped me solving this one. Two thing worth mentioning:
- if you buy high sell low, your profit is 0, not negative (well that’s what the test result told me and you should ask this first in reality).
- You are not really making transactions until you figure out where to buy in and sell out to maximize the profit.
So suppose you can predict the future and have the price array in hand:
[5, 4, 1, 2, 8, 6, 9]
In this case you should buy in at price 1 and sell out at 9. It looks like a simple question looking for just min and max value. However, consider the following:
[5, 4, 9, 2, 8, 6, 1]
Well in this case, you should buy in at price 2 but sell out at 8, but the min is still 1 and max is still 9. So be careful.
The simplest way would be using 2 loops and find out the max profit of you buying at each price. But that would take O(n^2) time. So can we do better than that?
From here I have two ways of thinking: one that is a bit more logical that following the above question (but I figured it out after I solved the problem) and the other that is a bit jumpy (but that was how I solved the problem in the first place).
The first way:
Well what is taking so long is that we are going two passes, what if we could just use one pass? We scan the array and keep updating the max profit along the way? How can we do that? Well surely we need something to keep track of the max profit. Do we need something else? I’m stuck here. And when you are stuck, try a simple example:
[5, 4, 1, 2, 8, 6, 9]
Suppose we are scanning and at price 8. And this moment, what is the max profit we can get? It’s 7. How do we get it? We buy in at price 1 and sell at 8. But wait, right now we only keep track of the max profit. We don’t know where we are planning to buy (well I know, and you know, in the brain, but the computer doesn’t since nothing is keeping track of it). So, it looks like we should keep track of two things:
- Based on what we have scanned, the price we are going to buy in (the current minimum).
- Based on what we have scanned, the current maximum profit we can make.
How to update?
- If the current price is lower than the current min, we can’t make any profit, so we keep the current max profit but update the current min price (and hope this new min can give us a higher profit later. Sadly we can’t go back in the opposite direction. See the first two examples).
- If the current price is higher than the current min, then we can make a profit: If the new profit is higher, we update the current max profit but keep the same min price. Otherwise, we do no update on both variables.
I believe this is an O(n) time algorithm since we are doing one scan and nothing more.
The second way:
Well this one is a bit jumpy. I have been reading about recursion lately. So I thought why not try solving it with recursion? So use recursion, we need to identify a similar problem with a smaller size. For example, to find the max profit of [5, 4, 1, 2, 8, 6, 9], is to find the max profit of [4, 1, 2, 8, 6, 9] and then do something with 5. But what exactly? Well, our goal is to get the max profit. Is it possible that we could update the max profit with 5? That depends. If the difference between 5 and the maximum of [4, 1, 2, 8, 6, 9] is greater than the older max profit, we update. Otherwise we don’t. This indicate that we need to keep track of the max profit and the maximum price at the same time. Unfortunately, Java cannot return multiple values but we can wrap them in an object, or wrap one of them in an Integer object. This algorithm works, until it hit a big input and reported a stackoverflow error. We will fix it later.
We can also think of another way: a similar problem but in the opposite direction. We look at [5, 4, 1, 2, 8, 6] and 9. We get the max profit of the latter and do something with 9. Whether to update the max profit depends on the difference between 9 and the previous low price we are supposed to buy in. This algorithm works, and it has a nice tail recursion form, until it hit a big input with stackoverflow error.
Usually when this happens, we could think about converting the recursion to iterative form, especially if we have tail recursions:
- If our recursion is not tail recursion, try making it tail recursion. One tip I find useful is to look at similar problem with smaller size in the opposite direction, like the example above. And the recursion function should take the returning value as an argument along with whatever we are keeping track of. Then return the result in the base case. It’s a bit vague here so see the code for clarification. I got this though from the Scala course on Coursera. Maybe it helped. Well correlation doesn’t mean causation.
- Once we have the tail recursion, we change it to iterative form by using our own Stack. We may need more than one stack, depending on how many variables we are keeping track of, in our case, two–one for max profit and the other for the low price to buy in. Put the body of the recursion in a while loop. At the beginning of the loop, pop out values from the Stack. For those tail recursion calls, we can just push the values of the arguments we are passing back to the stack. Again, check the code.
This actually ends up with the same iterative algorithm in the first approach. It has been a very interesting experience. I learned a lot in the second approach but it took longer. However, if I started with the first approach in the first place, would I be able to figure out the solution?
- Always keep recursion in your toolkit and think about smaller problems in both directions.
- You can convert tail recursion into iterative algorithm.
- Start with brutal-force and think about where and how we can improve (the running time of each procedure and which one can be faster?). By think, I mean really put ourselves in the situation and walk through (like “if we can solve it in one pass, what would it be like? To realize it, what do we need? Can we get it somehow?”).
Code on github: