我正在寻找一种更有效的蛮力替代方法，以找到具有非负数和的数组中最长的子数组。该数组中数字的范围是-5到5。
例如，如果您有一个数组A：
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]。如果最佳后缀比最佳解决方案要长，我们会将最佳解决方案更新为最佳后缀。
A[i]
后缀将由夹在两个正子阵列之间的负子阵列组成。因此，在这种情况下，从左到右开始：
4 2是第一正子阵列-5是负子阵列3 0 -2是第二正子阵列
然后程序检查两个正子数组的和是否大于负子数组。如果是这样，则整个最佳后缀将成为新的第一个正子数组。如果不是，则转储第一个正子数组和负子数组，而第二个正子数组变为第一个子数组，依此类推。
从理论上讲，程序应该能够逐步检查线性时间的最佳解决方案。
但是这个答案似乎是不正确的。
因此，我正在为此寻求更好的解决方案，或者至少暗示了一个更好的方向
任何帮助，将不胜感激！
这称为“最长偏差间隔”，是生物学中的常见问题。这是算法（在您的情况下L==0）：
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。
这是概念的说明：
