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.