Straight Developer

Given a log of stock prices compute the maximum possible earning.

the MaxProfit exercise is the second task from the Maximum slice problem lesson (9th lesson) on Codility.com and in this article I am going to share with you a O(N) time complexity 100% score javascript solution but before here’s the task description on codility.com:

Codility MaxProfit task description

An array A consisting of N integers is given. It contains daily prices of a stock share for a period of N consecutive days. If a single share was bought on day P and sold on day Q, where 0 ≤ P ≤ Q < N, then the profit of such transaction is equal to A[Q] − A[P], provided that A[Q] ≥ A[P]. Otherwise, the transaction brings loss of A[P] − A[Q].

For example, consider the following array A consisting of six elements such that: A[0] = 23171 A[1] = 21011 A[2] = 21123 A[3] = 21366 A[4] = 21013 A[5] = 21367

If a share was bought on day 0 and sold on day 2, a loss of 2048 would occur because A[2] − A[0] = 21123 − 23171 = −2048. If a share was bought on day 4 and sold on day 5, a profit of 354 would occur because A[5] − A[4] = 21367 − 21013 = 354. Maximum possible profit was 356. It would occur if a share was bought on day 1 and sold on day 5.

Write a function,

function solution(A);

that, given an array A consisting of N integers containing daily prices of a stock share for a period of N consecutive days, returns the maximum possible profit from one transaction during this period. The function should return 0 if it was impossible to gain any profit.

For example, given array A consisting of six elements such that: A[0] = 23171 A[1] = 21011 A[2] = 21123 A[3] = 21366 A[4] = 21013 A[5] = 21367

the function should return 356, as explained above.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [0..400,000];
• each element of array A is an integer within the range [0..200,000].

Codility MaxProfit task solution with javascript (100% score)

The solution is straight forward and uses the same approach as the last solution in codility PDF chapter 9: Maximum slice problem.
First of all, we create a new array and name it profits, this array will contain the profit or loss between the value of each cell and the one next to it (i & i+1), to do so, we loop over the main array A and calculate the difference like the following:

for(var i=0;i<A.length-1;i++){
        var current=A[i]
        var next=A[i+1]
        var difference=next-current
        profits.push(difference)
    }

Once we obtain the array of differences, all we have to do now is to find which slice of the array has the largest sum which can be obtained using this code:

 for(var p of profits){
        max=Math.max(0,max+p)
        bestProfit=Math.max(bestProfit,max)
    }

Here’s the final code:

function solution(A) {
    var profits=[]
    var max=0
    var bestProfit=0
    for(var i=0;i<A.length-1;i++){
        var current=A[i]
        var next=A[i+1]
        var difference=next-current
        profits.push(difference)
    }
    for(var p of profits){
        max=Math.max(0,max+p)
        bestProfit=Math.max(bestProfit,max)
    }
    if(bestProfit<0)
    return 0
    return bestProfit
}

Understanding Codility O(n) final solution on the max slice lesson (chapter 9 pdf)

as it’s already been said in the lesson pdf file on Codility, the implementation of this solution is simple however understanding it might be challenging at first so let me simplify it for you:
to understand this solution let us suppose that our array contains only positive numbers, if this is true then the maximum slice would be inevitably the whole array, and the largest sum would become the total sum of the array right ?
for example:

profits=[ 4, 5, 2, 1 ]

the largest possible sum here is 12 which equals the overall sum of the array itself

so calculating the largest sum of an array containing only positive numbers is as simple as calculating the total sum the whole array:

 for(var p of profits){
        max+=p
    }
return max

but what if we add some negative values to the array?

profits=[ 4, 5, -10, 2 , 1 ]

would the largest possible sum of the array equals the overall sum of it ? of course not, the largest sum here becomes 9 while the overall sum is 2 so our previous rule is no more valid because once negative values are included, the overall sum of the array decreases accordingly making it possible to have a slice that has a larger sum than the overall sum.
to deal with this, all we have to do is to loop on the array like if we’re trying to calculate the total sum of it, but this time, we reset the sum to zero each time the sum reaches a negative number:

max=Math.max(0,max+p)

this is equivalent to

if(max+p<0)
   max=0
else
   max+=p

and the loop should look like:

 for(var p of profits){
        max=Math.max(0,max+p)
        bestProfit=Math.max(bestProfit,max)
 }