寻找最长的非负子数组

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是第二个正子数组

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

理论上，该程序应能够在线性时间内逐步检查最佳解。

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

因此，我正在寻找更好的解决方案，或者至少是朝更好的方向的提示。

任何帮助都将不胜感激！

- ateymour

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。

以下是该概念的示例：

- Tyler Durden

Answer 2

提示

您可以通过以下方式在线性时间内完成：

1. 首先计算数组A的累加和
2. 然后计算一个数组B，给出索引i右侧A中的最大值
3. 并计算一个数组C，给出索引i左侧A中的最小值

数组B和C都将是非递增数组。

然后对于数组C中的每个起始位置，计算数组B中最大的结束位置，使得B[end]>C[start]。这可以通过以下方式在线性时间内完成：

1. 从start=0开始
2. 递增end直到B[end+1]<=C[start]
3. 递增start并返回步骤2

end-start的最大值对应于最长的子数组。

解释

主要思想是一旦您有了数组的累加和，就可以通过减法计算子数组的值。

例如，数组：

4 2 -5 3 0 -2 

具有累积值：

A = [4 6 1 4 4 2]

因此，要找到第二个、第三个、第四个条目（索引为1、2、3，其值分别为2、-5、3）的总和，我们可以计算：

A[3]-A[0] = 4 - 4 = 0

那么你现在的问题就是找到数组A中距离最远且满足A[end]>A[start]的数值对。

- Peter de Rivaz

Answer 3

在使用动态规划从左到右移动时，您可以为每个元素跟踪11个事项。这些11个事项对应于以下可能的总和：
-5、-4、-3、-2、-1、0、1、2、3、4、5
对于每个总和，您需要存储最左边的索引，使得从该索引开始并以当前索引结束的子数组的总和等于该总和。
这不是一个完整的解决方案，但我相信这可能会起到提示作用。

- user3288651