How do I get arrayMaxConsecutiveSum from CodeSignal more efficient?

user_4877345 0
Viewed 614

I am working through some problems on CodeSignal. I came across this one, arrayMaxConsecutiveSum. I got it to pass almost all tests, but it is timing out on the last one. If I move the test into custom tests, it passes there, so I'm not sure what to do. How do I code it better so that it doesn't time out?

Problem:

Given array of integers, find the maximal possible sum of some of its k consecutive elements.
Example:
For inputArray = [2, 3, 5, 1, 6] and k = 2, the output should be arrayMaxConsecutiveSum(inputArray, k) = 8. All possible sums of 2 consecutive elements are:
2 + 3 = 5;
3 + 5 = 8;
5 + 1 = 6;
1 + 6 = 7.
Thus, the answer is 8.

function arrayMaxConsecutiveSum(inputArray, k) {
    let max = 0;
    
    for(let i = 0; i < inputArray.length; i++){
        let sum = 0;
        let newArr = inputArray.slice(i, i + k);
        sum = newArr.reduce((accumulator, currentVal) => accumulator + currentVal);
        if(sum > max){
            max = sum;
        }
    }
    
    return max;
}

Error: Tests passed: 19/20. Execution time limit exceeded on test 20: Program exceeded the execution time limit. Make sure that it completes execution in a few seconds for any possible input.

max sum arrays javascript
2 Answers

Your current algorithm is O(n ^ 2) because it requires a nested loop.

You can make it O(n) by using a rolling sum instead. Start with the sum of elements 0 to k, then on each iteration, subtract the earliest element that makes up the sum and add the next element not included in the sum yet.

For example, with a k of 2:

  • start out with the sum of elements [0] and [1]
  • subtract [0], add [2], compare the new sum
  • subtract [1], add [3], compare the new sum

and so on.

function arrayMaxConsecutiveSum(inputArray, k) {
    let rollingSum = inputArray.slice(0, k).reduce((a, b) => a + b);
    let max = rollingSum;
    for(let i = 0; i < inputArray.length - k; i++){
        rollingSum += inputArray[i + k] - inputArray[i];
        max = Math.max(max, rollingSum);
    }
    return max;
}

console.log(arrayMaxConsecutiveSum([2, 3, 5, 1, 6], 2));

user_95152070 

function arrayMaxConsecutiveSum(inputArray, k) {

    var max = inputArray.slice(0,k).reduce((a,b)=>a+b);
    var cur = max;
    for(var i = k; i < inputArray.length; i++) {
        cur = cur + inputArray[i] - inputArray[i-k];
        if(cur>max)
            max = cur
    }
        return max

}


console.log(arrayMaxConsecutiveSum([2, 3, 5, 1, 6], 2));

user_137198130
Related