title: Finding the longest non-negative sub array
body: <p>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.</p>
  
  <p>For example, if you have an array <code>A</code>:</p>
  
  <p>4 2 -5 3 0 -2 -2 -3 4 -4 -3 -2 1</p>
  
  <p>then the longest non-negative sub array is </p>
  
  <p>4 2 -5 3 0 -2 -2 -3 4, with the length of 9</p>
  
  <p>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 <code>A[i]</code>. If the best suffix is ever longer than best solution, we update the best solution to the best suffix.</p>
  
  <p>The suffix would be made of a negative subarray sandwiched between two positive sub arrays.
  So, in this case starting from left to right:</p>
  
  <p>4 2 is the first positive sub array
  -5 is the negative sub array
  3 0 -2 is second positive sub array</p>
  
  <p>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.</p>
  
  <p>In theory the program should be able to incrementally check for the best solution in linear time.</p>
  
  <p><strong>But this answer seems to be incorrect.</strong></p>
  
  <p>So Im looking for a better solution for this, or at-least a hint towards a better direction</p>
  
  <p>Any help would be appreciated!</p>