如何更有效地从 CodeSignal 获取 arrayMaxConsecutiveSum？

Question

我正在解决 CodeSignal 上的一些问题。我遇到了这个，arrayMaxConsecutiveSum。我让它通过了几乎所有测试，但最后一个测试超时了。如果我将测试移到自定义测试中，它会在那里通过，所以我不确定该怎么做。我如何更好地编码以使其不会超时？

问题：

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;
}

错误：通过的测试：19/20。 Execution time limit exceeded on test 20: 程序超出了执行时间限制。确保它在几秒钟内完成对任何可能输入的执行。

Answer 1

您当前的算法是O(n ^ 2)，因为它需要嵌套循环。

您可以 O(n) 改为使用滚动总和。从元素 0 到 k 的总和开始，然后在每次迭代中，减去最早构成总和的元素并添加下一个尚未包含在总和中的元素。

例如，k 为 2:

从元素 [0] 和 [1] 的总和开始
减[0]，加[2]，比较新的和
减[1]，加[3]，比较新的和

等等。

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));

Answer 2

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));

如何更有效地从 CodeSignal 获取 arrayMaxConsecutiveSum？

How do I get arrayMaxConsecutiveSum from CodeSignal more efficient?

javascript

arrays

sum

max