Max Double Slice Sum – Codility 100% Correct Javascript Solution

The Max Double Slice Sum was a challenging problem to solve in O(N) complexity.

I iterated through the array from both sides finding out at each position the maximum sum of slices created up until that position (from the left or from the right).

At each step I tested to see which is the maximum :

• 0 or the maximum slice possible on left + the current element for the left slices
• 0 or the maximum slice possible on the right + the current element for the right slices

Once these arrays are formed, I iterated once through the first array in order to check at each element if the current sum between the maximum slice possible in its left and the maximum sum possible to its right at that index is going to be the overall maximum or not.

Solution in Javascript and O(N) complexity

function solution(A) {
    var sumsFromLeft = A.map(i => 0);
    var sumsFromRight = A.map(i => 0);

    //a fun opportunity to use a double condition and indexes in a for loop
    for (var indexLeft = 1, indexRight = A.length-2; indexRight >= 2; indexLeft++, indexRight--) {
        //verify with 0, minimum max sum is 0 anyway
        sumsFromLeft[indexLeft] = Math.max(0, sumsFromLeft[indexLeft-1] + A[indexLeft]);
        sumsFromRight[indexRight] = Math.max(0, sumsFromRight[indexRight+1] + A[indexRight]);
    }
    //initialize max with the first double slice sum
    var max = sumsFromLeft[0] + sumsFromRight[2];

    for (var i = 2; i < A.length-1; i++) {
        max = Math.max(max, sumsFromLeft[i-1] + sumsFromRight[i+1]);
    }

    return max;
    
}

And here is the description and the report of the solution.