找到最长的非负子数组

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）：

\n\n

Input: A nonempty array of n real numbers `A[1 . . . n]` and a lower bound `L`.\n\nOutput: The start and end index of the longest segment of `A` with sum at least `L`.\n\nC[0 . . . n] and M[0 . . . n] are arrays of size n +1, as defined in the context.\n\nM[0]\xe2\x86\x90C[0]\xe2\x86\x900; x\xe2\x86\x90y\xe2\x86\x900;\nfor i\xe2\x86\x901 to n do\n    C[i]\xe2\x86\x90C[i \xe2\x88\x921] + A[i];\n    if C[i \xe2\x88\x921]<C[M[i \xe2\x88\x921]] then M[i]\xe2\x86\x90i \xe2\x88\x921 else M[i] = M[i \xe2\x88\x921];\n    k\xe2\x86\x90i \xe2\x88\x92y +x \xe2\x88\x92 1;\n    while k >0 do\n        if C[i] \xe2\x88\x92 C[M[k]] >= L then k\xe2\x86\x90M[k] else break;\n        x\xe2\x86\x90k +1; y\xe2\x86\x90i;\n    end while\n    OUTPUT A(x, y);\nend for\n

\n\n

参见 Chen、Kuan-Yu 和 Kun-Mao Chao。“用于定位满足总和或平均约束的最长和最短线段的最佳算法。” 信息处理快报 96.6 (2005): 197-201。

\n\n

下面是这个概念的说明：

\n\n

\n