Finding the index such that all partial sums are nonnegative

Question

Given an array a[] of integers of arbitrary size N that sum to 0 (for example, a[] = {-1, 0, 5, 3, -9, 2}), does there always exists an index i ($0\le i\le N-1$) such that each partial sum $S_j = \sum_{k=i}^ j a_{k\pmod N}$ (with $N+i-1\ge j\ge i$) is nonnegative?

In the example a[] = {-1, 0, 5, 3, -9, 2} where $a_0 = -1, a_1 = 0, ... a_5 = 2$ (and we can check that $\sum_{k=0}^{5} a_k=0$), we can start from $i=5$ so that the partial sums $2, 2-1, 2-1+0, 2-1+0+5, 2-1+0+5+3, 2-1+0+5+3-9$ are all nonnegative.

If we can prove that such index $i$ always exists, what's an efficient algorithm to find the index $i$? There's an obvious $O(N^2)$ algorithm, but can we do it in $O(N)$? Thanks.

Note: this problem is somewhat similar to another problem: given an array of integers $a_0,a_1,a_2,...,a_n$ (they don't have to add up to 0), find $\max_{0\le i\le j\le n}\sum_{k=i}^j a_k$. This can be solved in time $O(n)$ as follows:

int maxsum = INT_MIN;

int sum = 0;

for (int i=0; i < a.length(); ++i){

if (sum <= 0) {sum = a[i]; }

else {sum += a[i];}

maxsum = max(sum, maxsum);

}

But in my original question, we are allowed to loop around, and we're required to find the index. So there are at least two differences between the two problems.

Answer 1

Let $b_0=a_0+1$ and $b_k=a_k$ for $1\le k\le N-1$; $\langle b_0,\ldots,b_{N-1}\rangle$ is an integer sequence whose sum is $1$. Raney’s lemma says that there is an index $k$ such that every partial sum of the shifted sequence $\langle b_k,b_{k+1},\ldots,b_{k+N-1}\rangle$ is positive, where the indices are computed mod $N$. Since these are integer sequences, it follows that every partial sum of $\langle a_k,a_{k+1},\ldots,a_{k+N-1}\rangle$ is non-negative, the indices again being computed mod $N$. The link includes a proof of Raney’s lemma, which is given in more detail on page $360$ of Graham, Knuth, & Patashnik, Concrete Mathematics, second edition, together with a generalization of the lemma.

If you examine the proof closely, you’ll find that you can compute $k$ in the following way. If $s_j$ is the $j$-th partial sum of the original sequence, let $t_j=s_j-\frac{j}N$; then the desired index $k$ is the one that minimizes $t_k$. For example, for your sequence $\langle -1,0,5,3,-9,2\rangle$ we have

$$\langle t_0,t_1,t_2,t_3,t_4,t_5\rangle=\left\langle-1,-\frac76,\frac{22}6,\frac{39}6,-\frac{16}6,-\frac56\right\rangle\;,$$

with minimum element $t_5$. This computation is $O(N)$.

Answer 2

Thank you, Brian. Actually I came up with my own algorithm for this problem (also $O(N)$): call the array a[]

The logic is as follows: Keep in mind that the sum of the entries is 0. Starting from index i=0, and compute the partial sums a[i], a[i]+a[i+1], ..., Once a[i] + ... + a[j] becomes negative (where $j\ge i$), restart from i = j+1, and repeat again. But once the number of summand in the partial sum is equal to the length of the array, we are done (return i).

This works because if a[i], a[i]+a[i+1], ..., a[i]+...+a[j-1] are nonnegative, but a[i]+...+a[j] is negative, we know the answer cannot be any of i, i+1, ..., j. So we restart from i = j+1.

int i=0; while (true){

int sum = 0; int j = i; count = 0;

while (sum >= 0 && count < a.size()){

sum += a[ j% a.size() ];

++j; ++ count;

}

if (count == a.size()) {return i;}

i = j;

}