Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Does anyone know of an algorithm that finds contiguous sublists of a list with positive sum? Preferably in O(n). I'm more interesting in the max length of those lists.

Thank you in advance.

share|improve this question
    
If you constrain your sublist to either start or end on a non-negative number, it is quite easy to do in linear time. However, I don't see how to generalize this. –  beauby Nov 17 '12 at 5:34
    
That's much more better than the O(n^2) algorithm I have now. Can you be more specific? If the list starts with a non-negative integer how will you proceed? –  panos Nov 18 '12 at 17:22

1 Answer 1

Let $x_1, \dots, x_n$ be a sequence of integers. Let $p_0, p_1, \dots, p_n$ be the prefix sums of $(x_i)$. In terms of prefix sums, we want to find $\max_{i \leq j} \{j - i ; p_j - p_i \geq 0\}$.

So in other terms, we want to find two points such that the first one has smaller value than the second, and such that they are as far apart as possible. Hence, for a given left point $p_i$, considering an other left point $p_{i+k}$ such that $p_i \leq p_{i+k}$ cannot lead to a better pair. Similarly, an endpoint of smaller value on the left cannot lead to a better pair.

In order to take advantage of this fact, we can construct the sequences $s_0, \dots, s_k$ and $e_0, \dots, e_l$ of potential start / end points as following:

  • $s_0 = 0$ and $s_{i+1} = \min\{j ; p_j < p_{s_i}\}$ (while such a $j$ exists)
  • $e_l = n$ and $e_{i-1} = \max\{j ; p_j > p_{e_i}\}$ (construct this one in reverse order since you do not know $l$ before actually constructing it)

Following the previous remark, an optimal subsequence will necessarily start on some $s_i$ and end on some $e_j$ (such that $s_i \leq e_j$).

Finally, we do a sweeping algorithm:

  • start with $s = s_0$ and $e = \max\{j ; p_{e_j} \geq p_{s_0} \}$.
  • then move to $s = s_1$ and increase $e = e_j$ as much as possible
  • then repeat the previous step until $s = s_k$ or $e = e_l$.

This last part has linear complexity.

This gives the idea of a linear algorithm to solve your problem. If there is need, I can write a more formal description and / or proof, but I think the important ideas are here. As for my previous comment, I was thinking under the assumption that each partial sum had to be non-negative as well, so you can disregard it.

share|improve this answer
    
Sorry, I had originally written "This last part clearly has linear complexity", but then figured that it was not so clear, and for some reason I deleted the word "linear" instead of "clearly". –  beauby Nov 23 '12 at 2:48
    
THANK YOU No need for further details or a proof, I can take for here. Thanks again for your time. –  user50516 Nov 24 '12 at 13:33
    
You're welcome. Please accept the answer if you find it suitable :) –  beauby Nov 24 '12 at 15:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.