Codility Max Profit

In this article I will provide a solution to the Max Profit sample Codility problem. The problem description is copyrighted, so have a look at the link for the description. The gist of it is:

You are given an array \(A\) of stock prices over a period of \(N\) days. Calculate the maximum possible profit (you are allowed to buy only once, and sell only once at any following date).

This problem is extremely similar to the maximum subarray problem which is solved in time \(O(n)\) using Kadane’s algorithm.

For the maximum profit, the gist is that we want to buy as low as possible, and sell as high as possible. Kadane’s algorithm part will keep track of the highest possible profit so far, and another variable will keep track of the minimal buy cost we’ve encountered so far, so this is always the one we should prefer.

An implementation in Java that scores 100/100 in Java might look like this:

public int maxProfit(int[] A) {
    if(A.length == 1 || A.length == 0){
        return 0;
    }
    
    int maxSoFar = 0;
    int maxEndingHere = 0;
    int minPrice = A[0];
    
    for(int i = 1; i < A.length; i++){
        maxEndingHere = Math.max(0, A[i] - minPrice);
        minPrice = Math.min(minPrice, A[i]);
        maxSoFar = Math.max(maxEndingHere, maxSoFar);
    }
    
    return maxSoFar;
}