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

Question

例如：{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

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