arrays - 数组的 n 个连续元素的最大总和

Question

如何找到数组中 n 个连续数字的最大总和？例如，如果我们的数组是 {2,5,3,4,6} 和 n == 2 那么输出应该是 10(即6 + 4).

对于较小的数组大小值和较小的 n 值，我能够获得正确的逻辑。但是当数组大小和 n 太大时，比如大约 10⁵，我的代码会花费很多时间。请提出优化方法。

我的代码被截断了:

for(int i = 0; i <= n - h; i++) {
  int count = 0;
  for(int k = i; k < i + h; k++) {
    count = count + arr[k];
  }
  if(i == 0) {
    ans[z] = count;
  } else if(i != 0) {
    if(count < ans[z]) {
      ans[z] = count;
    }
  }
  count = 0;
}

Answer 1

我的想法是:遍历数组从0到(array length - N)，求下N项的和，表达式如下:
下一个 N 项的总和 = 前一个总和 - 前一个子数组中的第一项 + 下一个子数组中的最后一项

示例:

数组 = {2,5,3,4,6}

当 i = 0 时，总和 = (2 + 5) = 7，最大总和 = 7

当 i = 1 时，sum = 7 - 2 + 3 = 8，因为 8 > 7，所以最大 sum = 8

当 i = 2 时，sum = 8 - 5 + 4 = 7，因为 7

当 i = 3 时，sum = 7 - 3 + 6 = 10，因为 10 > 8，所以最大 sum = 10

下面是c#中的示例代码

static int GetLargestSum(int[] array, int n)
{
    int largestSum = 0;
    int previousSum = 0;

    for (int i = 0; i <= array.Length - n; i++)
    {
        if (i == 0)
        {
            for (int j = 0; j < n; j++)
            {
                largestSum += array[j];
            }

            previousSum = largestSum;
        }
        else
        {
            int currentSum = previousSum - array[i - 1] + array[i + n - 1];
            if (currentSum > largestSum)
            {
                largestSum = currentSum;
            }
            previousSum = currentSum;
        }
    }

    return largestSum;
}