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

Question

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

我能够为数组大小和小值的小值获得正确的逻辑n.但是当数组大小和n太大,大约10 ^5时,我的代码需要花费很多时间.请建议一种优化的方法.

我的代码剪断了:

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遍历到(数组长度 - N),并使用以下表达式确定下一个N项的
总和:下一个N项的总和=前一个和 - 前一个子数组中的第一项+下一个子数组中的最后一项

例:

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

当i = 0时,sum =(2 + 5)= 7,max sum = 7

当i = 1时,sum = 7 - 2 + 3 = 8,因为8> 7,所以max sum = 8

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

当i = 3时,sum = 7 - 3 + 6 = 10,因为10> 8,所以max 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;
}