在int []中找到最大和范围的最快方法 [英] Fastest way to find max sum range in int[]

问题描述

开始优化算法，然后讲到最后一部分。我有一个这样的整数数组：

Been optimizing an algorithm and came down to the last part. I have an array of integers like this:

[1，1，2，5，0，5，3，1，1]

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

我的要求如下：

1. 输入：要求和的整数数量


2. 最大和应该由彼此相邻的整数组成


3. 如果整数的值为0，则范围内的总和无效


4. 最大整数总和，并且返回每个整数的索引

1. input: numbers of integers to sum over
2. the max sum should consist of integers next to each other
3. if an integer has the value 0 the sum in the range would be invalid
4. the max sum of integers and the index of each integer is returned

预期结果：

给出2（2个通缉）的输入，并提及数组应返回
[8，[5，6] ]，其中8是索引5和6处的整数之和

Given input of 2 (2 wanted) with the array as mentioned should therefor return [ 8, [ 5, 6 ] ] where 8 being the sum of integers at index 5 and 6

给定3的输入（3个通配符），并提及数组，因此应返回
[9 ，[5、6、7]]，其中9是索引5、6和7的整数之和（请注意，即使索引3、4、5的整数具有较高的和，由于索引4为0，结果仍然无效）

Given input of 3 (3 wanted) with the array as mentioned should therefor return [ 9, [ 5, 6, 7 ] ] where 9 being the sum of integers at index 5, 6 and 7 (notice that even though integers at indexes 3, 4, 5 have a higher sum the result is invalid due to index 4 being 0)

我目前正在通过执行大量循环来管理此问题，但我想知道是否有人有更好的方法来实现此目标。我目前选择的编码语言是C＃-如果可能的答复是C＃，我将不胜感激。只要是最快的方法，就可以使用linq和其他精美的Math功能。

I'm currently managing this by doing a lot of looping, but was wondering if somebody had a better way of achieving this. My coding language of choice is currently C# - I would therefor appreciate if possible replies would be in C#. Any use of linq and other fancy Math features is ok as long as it's the fastest way.

推荐答案

我认为您可以解决此问题在线性时间内。首先，用一个非常小的数字（例如-2 ^ 30）替换所有0，以免影响我们的总和。

I think you can solve this in linear time. First, replace all 0s with a very small number (-2^30 for example) so that it won't affect our sum.

然后：

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]

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

You can probably avoid replacing zeros with a few extra conditions. if s[i] = sum of first i integers, then s[i] - s[k - 1] gives you the sum of the integers k through i.

编辑：
您可以在O（1）额外空间中执行以下操作：首先替换所有0。

Edit: You can do this in O(1) extra space like this: first replace all 0s.

然后：

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

To avoid replacing zeroes in the first solution, just skip k spaces ahead when encountering a zero. In the second solution, skip k or k + 1 (depends on how you choose to implement this special case) spaces ahead, but be sure to rebuild your cr variable when doing the skip!

这篇关于在int []中找到最大和范围的最快方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！