最大值连续子序列算法

此问题的输入是实数的数组A[1...n]。您需要找出通过总结A的连续子序列A[i],A[i+1],...A[j]的所有数字可以获得的最高值。如果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）这个问题，但它也可以解决线性时间的问题。

设计一个算法来解决线性时间上面描述的问题。以伪代码的形式呈现您的算法。
简要说明算法的工作原理和原因。
给出一个简单的解释，说明为什么你的算法确实在线性时间运行。

来源

2016-12-12 soapzi

如果我们不采取任何项目（因此该解决方案是一个空的子阵），我们有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，直到result并继续求和。 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-12 07:51:14

最大值连续子序列算法

回答

相关问题