3
$\begingroup$

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.

  • 0
    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?2012-11-18

1 Answers 1

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.

  • 0
    **THANK YOU** No need for further details or a proof, I can take for here. Thanks again for your time.2012-11-24