寻找最长非负子阵列 [英] Finding the longest non-negative sub array

问题描述

我正在寻找一个更有效的替代蛮力寻找一个数组中最长的子阵列与一个非负的总和。中的数字，此数组的范围从-5至5

I'm looking for an more efficient alternative to brute force for finding the longest sub array of an array with a non-negative sum. The numbers range from -5 to 5 in this array.

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

For example, if you have an array A:

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

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

则最长的非负子阵列

4 2 -5 3 0 -2 -2 -3 4，具有的长度9

4 2 -5 3 0 -2 -2 -3 4, with the length of 9

我在想解决的办法是保持一个最佳的解决方案的策略，和最好的后缀，其中最好的后缀总是与最后一个点检查结束 A [1] 。如果最佳后缀是有史以来长于最佳解决方案，我们更新为最好后缀的最佳解决方案。

The solution I'm thinking of is to keeping tack of a best solution, and a best suffix, where the best suffix always ends with the last point checked A[i]. If the best suffix is ever longer than best solution, we update the best solution to the best suffix.

后缀将作出的负子阵列两个正子阵列之间。 所以，在这种情况下，从左至右开始：

The suffix would be made of a negative subarray sandwiched between two positive sub arrays. So, in this case starting from left to right:

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

4 2 is the first positive sub array -5 is the negative sub array 3 0 -2 is second positive sub array

然后程序检查是否两个正子阵列的总和小于负子阵列更大。如果是这样，整个最好后缀变为新的第一正子阵列。如果没有，那么在第一正和负子阵列倾倒和第二正子阵列将第一子阵列，等等。

Then the program checks if the sum of two positive sub arrays is larger than the negative sub array. If so, the whole best suffix becomes the new first positive sub arrays. If not, then the first positive and negative sub array are dumped and the second positive sub array becomes the first sub array, and so on.

在理论上，该方案应该能够以增量为您在线性时间的最佳解决方案。

In theory the program should be able to incrementally check for the best solution in linear time.

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

因此​​，进出口寻找一个这是一个更好的解决方案，或者，至少朝更好的方向暗示

So Im looking for a better solution for this, or at-least a hint towards a better direction

任何帮助将是AP preciated！

Any help would be appreciated!

推荐答案

这就是所谓的最长的偏见区间，是生物学的一个常见问题。下面是该算法（在这里，你的情况→== 0 ）：

This is called the "longest biased interval" and is a common problem in biology. Here is the algorithm (where in your case 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

见陈，关宇，和坤茂超。 优化算法用于定位所述最长和最短的线段满足的总和或平均约束。信息处理快报96.6（2005）：197-201

See Chen, Kuan-Yu, and Kun-Mao Chao. "Optimal algorithms for locating the longest and shortest segments satisfying a sum or an average constraint." Information Processing Letters 96.6 (2005): 197-201.

下面是概念的说明：

这篇关于寻找最长非负子阵列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！