时间戳

首页 > 解决方案 > 如何更有效地从 CodeSignal 获得 arrayMaxConsecutiveSum？

javascript - 如何更有效地从 CodeSignal 获得 arrayMaxConsecutiveSum？

问题描述

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

问题：

给定整数数组，找出其中一些连续元素的最大可能和。
示例：
对于 inputArray = [2, 3, 5, 1, 6] 和 k = 2，输出应为 arrayMaxConsecutiveSum(inputArray, k) = 8。2 个连续元素的所有可能和为：
2 + 3 = 5;
3 + 5 = 8；
5 + 1 = 6；
1 + 6 = 7。
因此，答案是 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。测试 20 超出执行时间限制：程序超出执行时间限制。对于任何可能的输入，确保它在几秒钟内完成执行。

标签： javascriptarrayssummax

解决方案

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

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

例如，ak为 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));

推荐阅读