c# - 在 int[] 中找到最大总和范围的最快方法

Question

一直在优化算法，一直到最后一部分。我有一个这样的整数数组:

[ 1, 1, 2, 5, 0, 5, 3, 1, 1 ]

我的要求如下:

1. 输入:要求和的整数个数
2. 最大和应由相邻的整数组成
3. 如果整数的值为 0，则该范围内的总和无效
4. 返回整数的最大和和每个整数的索引

预期结果:

给定输入 2(需要 2 个)和所提到的数组，因此应该返回 [ 8, [ 5, 6 ] ] 其中 8 是索引 5 和 6 处的整数之和

给定输入 3(需要 3 个)和所提到的数组，因此应该返回 [ 9, [ 5, 6, 7 ] ] 其中 9 是索引 5、6 和 7 处的整数之和(请注意，即使索引 3、4、5 处的整数具有更高的和，但由于索引 4，结果无效为 0)

我目前通过大量循环来管理这个，但想知道是否有人有更好的方法来实现这个。我目前选择的编码语言是 C#——因此，如果可能的回复是 C#，我将不胜感激。可以使用任何 linq 和其他奇特的数学功能，只要它是最快的方法即可。

Answer 1

我认为你可以在线性时间内解决这个问题。首先，将所有的 0 替换为一个非常小的数字(例如 -2^30)，这样它就不会影响我们的总和。

然后:

let s[i] = sum of first i integers
let k = number of integers required
let max = -inf    
for ( int i = k; i <= N; ++i )
  if ( s[i] - s[i - k - 1] > max )
     max = s[i] - s[i - k - 1]

您可能可以避免用一些额外的条件替换零。如果 s[i] = 前 i 个整数之和，则 s[i] - s[k - 1] 给出从 k 到 i 的整数之和。

编辑: 您可以像这样在 O(1) 额外空间中执行此操作:首先替换所有 0。

然后:

max = cr = sum of first k integers.
for ( int i = k + 1; i <= N; ++i )
{
  cr = cr + numbers[i] - numbers[i - k] 
  if ( cr > max )
    max = cr; // also update positions
}

为避免在第一个解决方案中替换零，遇到零时只需向前跳过 k 个空格。在第二个解决方案中，跳过 k 或 k + 1(取决于您选择如何实现这种特殊情况)前面的空格，但请务必在执行跳过时重建您的 cr 变量!