determining lowest starting index for travelling around a circular array without a negative partial sum

Question

Suppose I have a circular array of integers, for example:

$$ [1,2,3,-4] $$

A trip starting at a particular index $i$, wrapping around, and ending right before index $i$ is successful if none of the partial sums are negative.

For instance, the trip starting at index $1$ has the following partial sums

$$ \langle 2,5,1,2 \rangle $$

The trip starting at index $2$ has the following partial sums

$$ \langle 3,-1,0,2 \rangle $$

Is it possible to determine the lowest starting index in $O(n)$ time with $n$ being the number of integers (assuming integer operations take constant time)?

The naive solution of just trying each possible trip in succession takes $O\left(n^2\right)$ time.

Here is an implementation of that algorithm in Python with each function annotated with its cost

# O( length of xs )
def trip_good(xs, i):
    t = 0 
    for it in [range(i, len(xs)), range(i)]:
        for j in it:
            t += xs[j] 
            if t < 0:
                return False

# O ( (length of xs)^2 )
def trip_index(xs):
    for i in range(len(xs)):
        if trip_good(xs, i):
            return i
    return len(xs)

The first thing I thought of in order to break the problem down into a similar-but-structurally smaller problem is combining multiple deltas into 1 by adding adjacent items in my circular array.

So, the following circular array:

$$ [1,2,-2,-1] $$

would map onto

$$ [3,-3] $$

But there doesn't seem to be a relationship between the existence of a solution for the shorter array and the existence of a solution for the larger array. Is there a way to break down this problem and solve it in linear (or possibly log-linear) time?

Answer 1

Let $f(k)$ be partial sum from $1$ up to $k$ (not including $k$, so $f(1) = 0$). If they are all positive, then we are done.

Otherwise let $x$ be the negative value with the largest absolute value, and $i$ been the first time we encounter it, ie $f \geqslant x$, $f(i) = x$.

If $j < i$ then we can't start our trip at position $j$ because partial sum from $i$ to $j$ will be $f(j) - f(i) < 0$.

And if the trip is possible (and it happens iff sum of all elements is non-negative), then we can start our trip in $j$: we will be able to make it to $i > j$ because $f(i) - f(j) \geqslant 0$, and encountering a negative value $x$ at $i < j$ will mean sum of all elements is $x + f(j) - f(i)$, which is negative as sum of two negatives.