c# - arrayMaxConsecutiveSum c#

Question

作为学习 c# 的一部分，我参与了代码信号挑战。到目前为止，除了标题中所述的测试外，一切对我来说都很好。

问题是当数组的长度为 10^5 且连续元素的数量 (k) 为 1000 时，我的代码无法在 3 秒内运行。我的代码运行如下:

int arrayMaxConsecutiveSum(int[] inputArray, int k) {

    int sum = 0;
    int max = 0;

    for (int i = 0; i <= inputArray.Length-k; i++)
    {
        sum = inputArray.Skip(i).Take(k).Sum();

        if (sum > max)
            max = sum;
    }

    return max;
}

网站所有可见测试运行正常，但是当涉及到隐藏测试时，在测试20中，出现错误，指出

19/20 tests passed. 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.

我也试过解锁解决方案但是在c#上代码和这个有点相似但是他没有使用LINQ。我还尝试将它与隐藏测试一起运行，但发生了同样的错误，这很奇怪，因为它甚至没有通过所有测试就作为解决方案提交。

有没有更快的方法来获取数组的总和？

我也想过解锁隐藏的测试，但我认为它不会给我任何具体的解决方案，因为问题仍然存在。

Answer 1

您似乎在为每个循环添加 k 个数字。这个伪代码应该更有效:

1. 取前 k 个元素的总和并将其设置为最大值。

2. 像以前一样循环，但每次从现有总和中减去 i-1 处的元素并添加 i + k 处的元素。

3. 像以前一样检查最大值并重复。

---

这里的区别在于每次循环中的加法次数。在原始代码中，您为每个循环添加 k 个元素，在此代码中，在每个循环中，您减去一个元素并将单个元素添加到现有总和中，因此这是 2 个操作与 k 个操作。随着大型数组的 k 变大，您的代码开始变慢。