arrayMaxConsecutiveSum c#

Question

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

问题是当数组长度为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 测试通过。测试 20 超出执行时间限制：程序超出执行时间限制。对于任何可能的输入，确保它在几秒钟内完成执行。

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

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

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

Answer 1

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

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

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

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

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