在一个整型数组中找到最大和的范围的最快方法

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和其他高级数学功能，只要它是最快的方式。

- Tim Skauge

---

抱歉，我已经发布了一个答案。虽然它不是用C#编写的。 - Aryabhatta

不，这绝对不是作业……要是真的是就好了。 - Tim Skauge

然后，您可以删除其他人添加的标记，而他们甚至没有进行验证。 - Dykam

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

- IVlad

---

第二种解决方案跳过的情况下加1。将零替换为非常小的数字需要与遇到的数字进行比较；跳过是一般解决方案，而且也不难。 - Svante

Answer 2

以下代码应该可以解决问题。性能将取决于要求和的范围大小。与在每次迭代中添加子集的朴素方法相比，元素越多，性能越好。

 int getSum(int[] arr, int wanted)
        {
            var pre = new int[arr.Length];
            pre[0] = 0;
            pre[1] = arr[0];
            int max = 0;
            int skip = 1;
            for (var i = 1; i < arr.Length; i++)
            {
                skip--;
                //if the sum is marked invalid with a zero skip
                var current = arr[i];
                //calculate the index once
                int preIndex = i + 1;
                if (current == 0)
                {
                    skip = wanted;
                    pre[preIndex] = pre[i];
                    continue;
                }
                //store the sum of all elements until the current position
                pre[preIndex] = pre[i] + current;
                //find the lower end of the range under investigation now
                var lower = i - wanted;
                //if we haven't reached the wanted index yet we have no sum or if 
                //it's less than wanted element since we met a 0 
                //just go to the next element
                if (lower < 0 || skip > 0)
                    continue;
                var sum = pre[preIndex] - pre[lower];
                if (sum > max)
                    max = sum;
            }
            return max;
        }

- Rune FS

Answer 3

"易于阅读"的代码被认为是"优化"吗？

int numberOfElements = 4;   //parameter
int[] numbers = new[] { 1, 1, 2, 5, 0, 5, 3, 1, 1 };    //numbers


int[] result =
     //cicle each element
    (from n in Enumerable.Range(0, numbers.Length - numberOfElements + 1)
     //keep the (n + numberOfElements) elements
     let myNumbers = from p in Enumerable.Range(n, numberOfElements)
                     select numbers[p]
     //keep the sum (if we got a 0, sum is 0)
     let sum = myNumbers.Contains(0) ? 0 : myNumbers.Sum()
     orderby sum descending     //order by sum
     select myNumbers)          //select the list
        .First().ToArray();     //first is the highest

考虑在 .NET 4 发布后添加 .AsParallel() 以提高性能。

- Alex Bagnolini

---

我感谢你使用linq给出的回复。Linq很强大，但是我更在意执行速度。如果我不用担心速度的话，我会寻找像这样的答案。你的代码能返回数组中正确的数字，但是没有返回numberIndexes和sum（仅按其排序）。不过，修改它以返回这些也不太难 :) - Tim Skauge

Answer 4

这是O(n)时间和O(1)空间，并且仅一次遍历数组。

static public int[] FindMaxSumRange(int[] data, int n)
{
    // two pointers showing the lower and upper bound of current running sum
    int upper = 0, lower = 0;
    // best result found yet
    int max_found = 0;
    int max_position = -1;

    while (lower <= data.Length - n) {
        int running_sum = 0;
        // prefill running sum with n items
        for (upper = lower; upper - lower < n && upper < data.Length; upper++) {
            if (data[upper] == 0) {
                // found a zero, set lower pointer to the next item
                lower = upper + 1;
                break;
            }
            running_sum += data[upper];
        }
        if (upper - lower != n) {
            // found a zero, restart at new lower position
            continue;
        }
        if (running_sum > max_found) {
            max_found = running_sum;
            max_position = lower;
        }
        while (upper < data.Length) {
            if (data[upper] == 0) {
                // found a zero, set lower pointer to the next item
                lower = upper;
                break;
            }
            running_sum += data[upper] - data[lower];
            if (running_sum > max_found) {
                max_found = running_sum;
                max_position = lower;
            }
            upper++; lower++;
        }
        lower++;
    }
    return new int[]{max_found, max_position};
}

这将返回最大总和及其找到的位置。如果您需要获取索引列表，只需构建范围[max_position，max_position + n)

- Ants Aasma

---

您当前的答案导致了一个无限循环。 - Tim Skauge

啊，除非测试过，否则没有东西可以正常工作的规则又生效了。终止条件有轻微错误，已经纠正了，谢谢。 - Ants Aasma

Answer 5

以下是一段牢骚，完全未经测试。甚至不确定它是否能编译。我将其留给其他人来改进。

using System;
using System.Linq;
public int[] max(int[] a, int amount) {
    var max = int.MinValue;
    var maxPos = 0;
    if (a.length < amount) return null;
    var c = 0;
    while (c == 0) {
        for (int i = 0; i < amount; i++) {
            if (a[i + maxPos] == 0) {
                c = 0;
                break; // try again
            }
            c += a[i];
        }
        if (c != 0) maxPos = i - amount;
    }
    if (c == 0) return null;
    max = c;
    for (int i = maxPos; i + amount < a.length; i++) {
        if(a[i] == 0) {
            i += amount - 1;
            continue;
        }
        c -= a[i];
        c += a[i + amount];
        if (c > max) {
            c = max;
            maxPos = i;
        }
    }
    if (c == 0) return null;
    var result = new int[amount + 1];
    result[0] = max;
    for (int i = 0; i < amount; i++)
        result[i + 1] = maxPos + i;
    return result;
}

- Dykam

Answer 6

思路如下： 1. 将数组分组以计算总和 2. 计算每个组的总和 3. 找出最大总和

以下是代码：

private Result GetMax(ICollection<int> items, int itemCount)
{
  return items.
    Take(items.Count - (itemCount - 1)).
    Select((value, index) => items.Skip(index).Take(itemCount)).
    Select((group, index) =>
      new Result
      {
        Index = index,
        Sum = group.Aggregate(0, (sum, i) => sum + (i == 0 ? int.MinValue : i))
      }).
    Max();
}

private struct Result : IComparable<Result>
{
  public int Index { get; set; }
  public int Sum { get; set; }

  public int CompareTo(Result other)
  {
    return Sum.CompareTo(other.Sum);
  }
}

- dh.

---

该算法速度快且易于阅读。不知道为什么这个Linq算法比其他提交的算法快那么多。 - Tim Skauge