计算数组O(N)中具有最大和的序列

Question

如果我想计算数组中具有最大和的序列，那么当我有O(n)时间复杂度的限制时，我怎么做呢？

例如：{1,2,3,4，-3}输出为4，因为1+2+3+4的和是最大和，该序列中有4个数字

我知道如何用O(N^2)时间复杂度来实现它，但不知道如何使用O(n)帮助？:)

Answer 1

我想你可以这样迭代：

MaxSum = 0;
CurrentSum = 0;
MaxLen = 0;
CurrentLen = 0;

Index = GetFirstPositiveValue(); 
// This function returns the first Index where Array[Index] > 0
// O(n) 

while (Index < Array.Length()) {
    // general loop to parse the whole array
    while (Array[Index] > 0 && Index < Array.Length()) {
        CurrentSum += Array[Index];
        CurrentLen++;
        Index++
    }
    // We computed a sum of positive integer, we store the values 
    // if it is higher than the current max
    if (CurrentSum > MaxSum) {
        MaxSum = CurrentSum;
        MaxLen = CurrentLen;
    }
    // We reset the current values only if we get to a negative sum
    while (Array[Index] < 0 && Index < Array.Length()) {
        CurrentSum += Array[Index];
        CurrentLen++;
        Index++;
    }
    //We encountered a positive value. We check if we need to reset the current sum
    if (CurrentSum < 0) {
        CurrentSum = 0;
        CurrentLen = 0;
    }
}
// At this point, MaxLen is what you want, and we only went through 
// the array once in the while loop.

从第一个积极因素开始。如果每个元素都是负值，那么只要选择最高值，问题就结束了，这是一个1元素序列。

只要我们有正数，我们就继续求和，所以我们有一个当前最大值。当我们有负值时，我们检查当前的最大值是否高于存储的最大值。如果是这样的话，我们用新的值替换存储的最大值和序列长度。

现在，我们把负数和起来。当我们发现另一个积极因素时，我们必须检查一下：

如果当前和是正的，那么我们仍然可以有这个序列的最大和。如果它是负的，那么我们可以丢弃当前的和，因为最大和将不包含它：

{1，-2,3,4}中，3+4大于1-2+3+4

只要我们还没有完成整个数组，就会重新启动这个过程。只有当我们有一个子序列产生负和时，我们才重新设置序列，并且只有当我们有一个更大的值时，我们才存储最大值。

我认为这是按预期工作的，我们只对数组进行了一两次。所以是O(n)

我希望这是可以理解的，我很难把我的想法说清楚。如果我不够清楚，用{1,2,3，-4,5} / {1,2,3，-50,5} / {1,2,3，-50,4,5}等小例子执行该算法可能会有所帮助:)