performance - Finding the longest non-negative sub array

Question

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.

For example, if you have an array A:

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

then the longest non-negative sub array is

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

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 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.

But this answer seems to be incorrect.

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

Any help would be appreciated!

Answer 1

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

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.

Here is an illustration of the concept: