{"id":416,"date":"2020-03-28T04:00:00","date_gmt":"2020-03-28T04:00:00","guid":{"rendered":"https:\/\/danwritescode.com\/?p=416"},"modified":"2020-06-26T05:08:21","modified_gmt":"2020-06-26T05:08:21","slug":"max-double-slice-sum-codility-100-correct-javascript-solution","status":"publish","type":"post","link":"https:\/\/danwritescode.com\/max-double-slice-sum-codility-100-correct-javascript-solution\/","title":{"rendered":"Max Double Slice Sum – Codility 100% Correct Javascript Solution"},"content":{"rendered":"\n
The Max Double Slice Sum was a challenging problem to solve in O(N) complexity.<\/p>\n\n\n\n
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).<\/p>\n\n\n\n
At each step I tested to see which is the maximum :<\/p>\n\n\n\n
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.<\/p>\n\n\n\n
function solution(A) {\n var sumsFromLeft = A.map(i => 0);\n var sumsFromRight = A.map(i => 0);\n\n \/\/a fun opportunity to use a double condition and indexes in a for loop\n for (var indexLeft = 1, indexRight = A.length-2; indexRight >= 2; indexLeft++, indexRight--) {\n \/\/verify with 0, minimum max sum is 0 anyway\n sumsFromLeft[indexLeft] = Math.max(0, sumsFromLeft[indexLeft-1] + A[indexLeft]);\n sumsFromRight[indexRight] = Math.max(0, sumsFromRight[indexRight+1] + A[indexRight]);\n }\n \/\/initialize max with the first double slice sum\n var max = sumsFromLeft[0] + sumsFromRight[2];\n\n for (var i = 2; i < A.length-1; i++) {\n max = Math.max(max, sumsFromLeft[i-1] + sumsFromRight[i+1]);\n }\n\n return max;\n \n}<\/code><\/pre>\n\n\n\n