在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为0,结果无效,4,5的总和较高

我现在通过做很多循环来管理这个,但是想知道是否有人有更好的方法来实现这一点.我选择的编码语言目前是C# - 如果可能的回复将在C#中,我会很感激.任何使用linq和其他花哨的数学功能都是可以的,只要它是最快的方式.

Answer 1

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

然后:

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变量!