寻找最长的非负子数组

Question

我正在寻找一种更有效的蛮力替代方法，以找到具有非负数和的数组中最长的子数组。该数组中数字的范围是-5到5。

例如，如果您有一个数组A：

4 2 -5 3 0 -2 -2 -3 4 -4 -3 -2 1

那么最长的非负子数组是

4 2 -5 3 0 -2 -2 -3 4，长度为9

我正在考虑的解决方案是保持最佳解决方案和最佳后缀，其中最佳后缀始终以最后检查的点结束A[i]。如果最佳后缀比最佳解决方案要长，我们会将最佳解决方案更新为最佳后缀。

后缀将由夹在两个正子阵列之间的负子阵列组成。因此，在这种情况下，从左到右开始：

4 2是第一正子阵列-5是负子阵列3 0 -2是第二正子阵列

然后程序检查两个正子数组的和是否大于负子数组。如果是这样，则整个最佳后缀将成为新的第一个正子数组。如果不是，则转储第一个正子数组和负子数组，而第二个正子数组变为第一个子数组，依此类推。

从理论上讲，程序应该能够逐步检查线性时间的最佳解决方案。

但是这个答案似乎是不正确的。

因此，我正在为此寻求更好的解决方案，或者至少暗示了一个更好的方向

任何帮助，将不胜感激！

Answer 1

这称为“最长偏差间隔”，是生物学中的常见问题。这是算法（在您的情况下L==0）：

Input: A nonempty array of n real numbers `A[1 . . . n]` and a lower bound `L`.

Output: The start and end index of the longest segment of `A` with sum at least `L`.

C[0 . . . n] and M[0 . . . n] are arrays of size n +1, as defined in the context.

M[0]←C[0]←0; x←y←0;
for i←1 to n do
    C[i]←C[i −1] + A[i];
    if C[i −1]<C[M[i −1]] then M[i]←i −1 else M[i] = M[i −1];
    k←i −y +x − 1;
    while k >0 do
        if C[i] − C[M[k]] >= L then k←M[k] else break;
        x←k +1; y←i;
    end while
    OUTPUT A(x, y);
end for

参见Chen，Kuan-Yu和Kun-Mao Chao。“用于找到满足总和或平均约束的最长和最短段的最佳算法。”
信息处理快报96.6（2005）：197-201。

这是概念的说明：