数组最大连续和 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。我还尝试与隐藏测试一起运行，但是出现了同样的错误，这很奇怪，因为它甚至没有通过所有测试就被提交为解决方案。

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

我还考虑解锁隐藏测试，但我认为这不会给我任何具体的解决方案，因为问题仍然存在。

- Dorokun192

---

你需要使用一个 O(N) 的算法来解决这个问题，例如 https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/ - Matthew Watson

Answer 1

似乎你在每次循环中都要做k个数字的加法。以下伪代码应该更有效率：

1. 取前k个元素求和，将其设为最大值。

2. 像之前一样循环，但每次从现有总和中减去第i-1个元素并加上第i + k个元素。

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

---

区别在于每次循环中进行加法操作的数量。在原始代码中，每次循环都要添加k个元素，而在这个代码中，在每个循环中你只需从现有的总和中减去一个元素并加上一个元素，因此这是2个操作与k个操作。对于大数组，当k变大时，你的代码开始变慢。

- Paddy

---

现在明白了，谢谢。我仍然不明白如何分离前三个元素可以使代码更有效率。我也想点赞，但是我的声望还不到15。 - Dorokun192

@Dorokun192，这取决于时间复杂度，你的是O(n*k)，而这个是O(n)。 - TheGeneral

Answer 2

针对这种情况，我建议您不要使用Skip方法，因为它每次都会迭代集合。您可以在此处检查Skip的实现。为了参考，复制代码。

    public static IEnumerable<TSource> Skip<TSource>(this IEnumerable<TSource> source, int count) {
        if (source == null) throw Error.ArgumentNull("source");
        return SkipIterator<TSource>(source, count);
    }

    static IEnumerable<TSource> SkipIterator<TSource>(IEnumerable<TSource> source, int count) {
        using (IEnumerator<TSource> e = source.GetEnumerator()) {
            while (count > 0 && e.MoveNext()) count--;
            if (count <= 0) {
                while (e.MoveNext()) yield return e.Current;
            }
        }
    }

正如您所看到的Skip每次迭代集合，如果您有一个巨大的集合，其中k是一个很高的数值，那么您会发现执行时间缓慢。

相反，您可以使用简单的for循环来迭代所需的项：

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

    int sum = 0;
    int max = 0;

    for (int i = 0; i <= inputArray.Length-k; i++)
    {
        sum = 0;
        for (int j = i; j < k + i; j++)
        {
            sum += inputArray[j];
        }

        if (sum > max)
            max = sum;
    }
    return max;
}

你可以查看这个dotnet fiddle -- https://dotnetfiddle.net/RrUmZX，在那里你可以比较时间差异。为了进行全面的基准测试，我建议看看Benchmark.Net。

- user1672994

---

两者的时间复杂度都是O(n*k)，但它只需要是O(n)。 - TheGeneral

@TheGeneral - 明白了。这可以通过Paddy提出的双指针方法以O(n)的时间复杂度完成。 - user1672994

使用dotnetfiddle，我的先前代码给了我1.67Mb的内存，执行时间为0.328秒。现在我看到新代码的巨大差异，它运行于最后运行时间：下午4:46:04 编译：0.156秒 执行：0秒 内存：813kb CPU：0秒。 - Dorokun192

Answer 3

是的，您不应该在大型列表上运行take和skip，但这里有一个纯LINQ解决方案，既易于理解又能在足够的时间内执行任务。是的，迭代代码仍然会比它表现更好，因此您必须为您的用例做出权衡。基准测试因大小或易于理解而异。

int arrayMaxConsecutiveSum(int[] inputArray, int k)
{
    var sum = inputArray.Take(k).Sum();
    return Math.Max(sum, Enumerable.Range(k, inputArray.Length - k)
        .Max(i => sum += inputArray[i] - inputArray[i - k]));
}

- Buvy

Answer 4

这是我的解决方案。

public int ArrayMaxConsecutiveSum(int[] inputArray, int k)
{
    int max = inputArray.Take(k).Sum();
    int sum = max;

    for (int i = 1; i <= inputArray.Length - k; i++)
    {
        sum = sum - inputArray[i- 1] + inputArray[i + k - 1];

        if (sum > max)
            max = sum;
    }
    return max;
}

- Carlos Alberto Medina Hdez

Answer 5

在使用LINQ时考虑到性能时需要小心。并不是它很慢，而是它很容易用单个单词隐藏一个大操作。在下面这行代码中：

sum = inputArray.Skip(i).Take(k).Sum();

Skip(i)和Take(k)都需要大约与for循环一样长的时间，遍历数千行数据，而且这行代码会在主循环中的每一个项目上运行。

没有什么神奇的命令可以更快，相反，您必须重新考虑您的方法，以在循环内执行最少的步骤。在这种情况下，您可以记住每个步骤的总和，只需添加或删除单个值，而不是每次重新计算整个值。

public static int arrayMaxConsecutiveSum(int[] inputArray, int k) 
{
    int sum = 0;
    int max = 0;

    for (int i = 0; i <= inputArray.Length-k; i++)
    {
        // Add the next item
        sum += inputArray[i];

        // Limit the sum to k items
        if (i > k) sum -= inputArray[i-k];

        // Is this the highest sum so far?
        if (sum > max)
            max = sum;
    }
    return max;
}

- Robin Bennett