Max Profit Codility – 100% Correct Solution

The Max Profit Codility challenge put me to a solid test in order to find a O(N) solution.

In the end I found the following algorithm:

I iterated the array of stock prices. At each point I calculated the maximum profit that could be obtained in point and the minimum price met until that point. Then I compared the maximum so far with the current maximum possible profit and kept the biggest one in the maxSoFar value.

Solution in Javascript with O(N) complexity

function solution(A) {
    let maxSoFar = maxEndingHere = 0;
    let minPrice = A[0]
    for (let i = 0; i < A.length; i++){
        maxEndingHere = Math.max(0, A[i]-minPrice)
        minPrice = Math.min(minPrice, A[i])
        maxSoFar = Math.max(maxEndingHere, maxSoFar)
    } 
    return(maxSoFar)
}

Here is a link to the report and the description of the problem.