Apple stocks interview question

Recently I stumbled upon this interview question on InterviewCake. Basically it goes like this: you have an array of stock prices, and you should calculate the highest profit you could get. For example, you have [2, 1, 4, 10, 7] — the highest profit is 10–1 = 9. What I didn’t like about the problem was that it didn’t require to find minimum and maximum stock prices you could obtain the best profit with, just the highest profit itself. So I decided to solve it with this clause. Besides, I believe it requires to delve into the nature of this problem a bit deeper.

After hanging around and re-reading the problem for I guess half an hour, hoping to come up with a solution, I decided to draw the diagram of how the stock prices evolve.

Here is the simplest beginning:

The best profit I could obtain so far is buy for $10 and sell for $20. How could this graph evolve? Well, there are actually only two scenarios that I’m interested in. If the next price is higher than the previous, I have a new highest price, and new highest profit. And if the next price is lower than the previous lowest price, I potentially have a lowest price that I should buy stock for. But I don’t know if later there will be a price that results in a new highest profit. It could be like that:

or like that:

So I need to introduce a concept of minimum price candidate, that is, a price that could be the one I should buy the stocks for. So when I find myself in point 3, I say that it is a candidate for the next minimum price. And if the stock at point 4 leads to higher profit (or, in other words, the highest so far), I pose that the candidate for minimum price actually becomes a minimum price, and the stock that brings me to the highest profit becomes the maximum price, that is, the price I should sell the stocks for.

So the following code seems fine from the first sight:

function getMaxProfit(array $stocks){$minCandidate = $min = $stocks[0];$max = $stocks[1];

**for** ($i = 1; $i < _count_($stocks); $i++) {  
    **if** ($stocks\[$i\] < $minCandidate) {  
        $minCandidate = $stocks\[$i\];  
    } **elseif** ($stocks\[$i\] - $minCandidate > $max - $min) {  
        $max = $stocks\[$i\];  
        $min = $minCandidate;  
    }  
}  

**return** \[$min, $max\];  

}

But there is a problem. What if stock prices go down the whole day, but the difference between the prices gets lower? For example, with this array — [10, 5, 2, 1] — I get an erroneous result. So I need to calculate the highest profit first, and then refresh $minCandidate if needed:

function getMaxProfit(array $stocks){$minCandidate = $min = $stocks[0];$max = $stocks[1];

**for** ($i = 1; $i < _count_($stocks); $i++) {  
    **if** ($stocks\[$i\] - $minCandidate > $max - $min) {  
        $max = $stocks\[$i\];  
        $min = $minCandidate;  
    }  

    **if** ($stocks\[$i\] < $minCandidate) {  
        $minCandidate = $stocks\[$i\];  
    }  
}  

**return** \[$min, $max\];  

}

That’s it.