Search for the longest non-negative helper array

Question

I am looking for a more effective alternative to brute force for finding the longest auxiliary array array with non-negative sum. 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 auxiliary array

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

The solution I think of is to stick with the best solution and the best suffix, where the best suffix always ends with the last point checked A[i]. If the best suffix is ​​longer than the best solution, we update the best solution for the best suffix.

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

4 2 - the first positive auxiliary matrix -5 - negative auxiliary array 3 0 -2 - the second positive auxiliary array

The program then checks to see if the sum of the two positive auxiliary arrays is greater than the negative auxiliary array. If so, then the best suffix will be the new first positive submatrix. If not, the first positive and negative auxiliary array are discarded, and the second positive auxiliary array becomes the first auxiliary array, etc.

Theoretically, the program should be able to incrementally check the best solution in linear time.

But this answer seems wrong.

, , ,

!

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

. , - - . " , ". 96,6 (2005): 197-201.

:

Answer 2

HINTS

:

• A
• B, i
• C, i

B C .

C B, , B [end] > C [start]. :

• = 0
• , B [end + 1] <= C [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].

Answer 3

11 , . 11 :
-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5
, , , ​​ .
, , .