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