算法 - 找到数组的起始索引，使元素之和保持 >= 0

Question

有人告诉我这可以在 O(n) 内完成 - 时间和 O(n) 内存使用。

作为输入，我收到一个 intigers 列表(数量为 n - 从一开始就可用)。

任务是找到最低索引(从左侧开始)，使我能够遍历数组(从起始索引到起始元素后面的索引做一个圆圈)，以便变量总和 - 即总结所有元素的方式永远不会低于 0。

*此数组中所有元素的总和始终为 0。

例如:1, -1, -3, 3, 4, -4

1. 1 - 1 - 3 = -2 < 0 不是那个
2. -1 < 0
3. -3 < 0
4. 3 + 4 - 4 + 1 - 1 - 3 = 0

很好，因为 7 > 0, 3 > 0, 4 > 0, 3 > 0, 0=0 :)

我现在这样做的方式是进入 for 循环 n 次，在里面我有两个 for 循环:一个用于 i->end 索引，另一个用于 0->i-1 索引。

这可行，但速度太慢，任何想法都值得赞赏。(所有基于语言的程序性能改进是不够的)

Answer 1

来自 https://www.quora.com/Does-there-always-exist-a-rotation-of-a-circular-array-such-that-all-prefix-sums-for-that-rotation-are-non-negative-Given-that-sum-of-all-its-elements-is-non-negative :

Let the sequence be a(1),a(2),...,a(N) . Define s_a(i) = a(1)+a(2)+...+a(i). It is given that s_a(N)≥0 (assumption). Let j be the largest index such that s_a(j)<0 if such a j exists. Obviously, j < N . Consider the sequence a(j+1),a(j+2),...,a(N). It is easy to see that all prefix sums of this sequence are ≥0. If a(j+1)+a(j+2)+...+a(k) were less than 0, s_a(k) would have been less than 0 as well, a contradiction.

Now generate a new sequence {bi} = a(j+1),a(j+2),...,a(N),a(1),a(2),...,a(j). It is easy to see that the prefix sums of this new sequence (call it s_b(i)) do not attain a value less than zero for the first N-j elements. Also, since s_b(N-j)≥0, Had s_a(i) been nonnegative, s_b(i+N-j) would be as well.

Keep repeating the process of taking the section after the rightmost position with a negative prefix sum and bringing it to the beginning of the sequence. At each step, the starting range in which we are assured that the prefix sums will be nonnegative keeps increasing. But this number is bounded by N, the length of the sequence. This means that after some steps, there will be no negative prefix sum in the sequence. Thus we have obtained a rotation of the original sequence with all prefix sums nonnegative.

这是我的想法的简单 O(n) 实现。

int best_index(std::vector<int> & a){
    int n = A.size();

    long long array_sum=0;
    long long sum=0;
    int last_index=-1;
    for (int i = 0; i < n; ++i)
    {
        array_sum+=a[i];
        if (sum<0)
        {
            sum=0;
            if (a[i]>=0)
            {
                last_index=i;
            }
        }
        sum+=a[i];
    }

    if (array_sum<0)
    {
        return -1;
    }
    return last_index;
}

复杂度:O(n)