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

Answer 2

如果知道长度为 N 的数组末尾的子数组的最大和，则可以简单地计算长度 N+1 之一的子数组：

[..., X]       has max subsum S
[..., X, Y]    has max subsum max(0, S + Y)

因为要么包含 Y，要么有一个空子数组（因为子数组位于列表末尾）。

您可以通过从空列表中构建以下内容来找到以任意位置结尾的子数组的所有最大总和：

[]             S = 0
[1]            S = 1
[1, 2]         S = 3
[1, 2, -4]     S = 0
[1, 2, -4, 5]  S = 5

然后您只需要跟踪最大值及其宽度。下面是一些 Python 演示算法的代码。

def ranges(values):
    width = cum_sum = 0

    for value in values:
        cum_sum += value
        width += 1

        if cum_sum < 0:
            width = cum_sum = 0

        yield (cum_sum, width)

total, width = max(ranges([-2, 1, 2, 3, -8, 4, -3]))

total, width
#>>> (6, 3)

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

count the sequence that has the max sum in array O(N)

algorithm

math

time-complexity