0

这个问题的输入是一个A[1...n]实数数组。A[i],A[i+1],...A[j]您需要找出通过将 的连续子序列的所有数字相加可以获得的最高值是多少A。如果A不包含负数，则问题很简单，可以通过将 的所有元素相加来解决A。A但是，当包含正数和负数的混合时，它变得更加棘手。

例如，对于A = [-2,11,-4,13,-5,-3]，解决方案是20 (11-4+13=20)。对于A = [-2,1,-3,4,-1,2,1,-5,4]，解为6 (4-1+2+1=6)。一个空子序列的个数之和是0。

在O(n^3)中存在解决此问题的蛮力解决方案，但也可以在线性时间内解决该问题。

  1. 设计一种算法，在线性时间内解决上述问题。用伪代码展示你的算法。
  2. 简要说明您的算法如何以及为何起作用。
  3. 简要解释一下为什么你的算法确实在线性时间内运行。
4

1 回答 1

0

如果我们不采取任何项目（所以解决方案是一个空子数组），我们有0一个解决方案。这就是为什么规则是：

 When running `sum` drops to `0` or below, restart summing.

一个有点棘手的时刻是在求和时遇到一个负数：

 3, 4, 5, -1 ...

我们可以留下它（并拥有3 + 4 + 5 == 12）或接受它，希望很快就会出现正数：

3, 4, 5, -1, 100, 200, 300

为了解决这种歧义，我们可以记住最好sum的 aresult并继续求和。C#实现：

private static double Solution(IEnumerable<double> source) {
  // We can guarantee 0 (for empty subarray) 
  double result = 0;
  double sum = 0; 

  // Linear: all we have to do is to scan the collection 
  foreach (var item in source) 
    if (sum + item <= 0) // when sum drops to zero
      sum = 0;           // ... restart summing
    else {
      sum += item;

      if (sum > result)  // update the best sum so far on each decision
        result = sum;
    }

  return result;
}

测试：

// 6
Console.WriteLine(Solution(new double[] { -2, 1, -3, 4, -1, 2, 1, -5, 4 }));
// 20
Console.WriteLine(Solution(new double[] { -2, 11, -4, 13, -5, -3 }));
于 2016-12-12T07:51:14.863 回答