algorithm - 计算数组 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} 等小示例执行此算法可能会有所帮助如果我不够清楚:)