算法 - 查找数组的起始索引,使元素之和保持> = 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 index而另一个用于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 -负数给定所有元素的总和是非负的：

\n\n

\n

令序列为 a(1),a(2),...,a(N) 。定义 s_a(i) =\na(1)+a(2)+...+a(i)。给出s_a(N)\xe2\x89\xa50（假设）。如果 j 存在，则令 j 为 s_a(j)<0 的最大索引。显然， j\n < N 。考虑序列 a(j+1),a(j+2),...,a(N)。很容易看出，这个序列的所有前缀和都是\xe2\x89\xa50。如果\na(j+1)+a(j+2)+...+a(k) 小于0，则s_a(k) 也将小于\n 0，这是一个矛盾。

\n\n

现在生成一个新序列 {bi} =\na(j+1),a(j+2),...,a(N),a(1),a(2),...,a(j ）。很容易看出，对于前 Nj 个元素，这个新序列（称为 s_b(i)）的前缀和的值不会小于零。另外，由于\n s_b(Nj)\xe2\x89\xa50，如果 s_a(i) 是非负的，则 s_b(i+Nj) 也将是非负的。

\n\n

继续重复使用负前缀和最右边位置之后的部分并将其带到序列开头的过程。在每一步中，我们确保前缀和为非负的起始范围不断增加。但是这个数字受到序列长度 N 的限制。这意味着经过一些步骤后，序列中将不存在负前缀和。因此，我们获得了原始序列的旋转，其中所有前缀和均为非负。

\n

\n\n

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

\n\n

int best_index(std::vector<int> & a){\n    int n = A.size();\n\n    long long array_sum=0;\n    long long sum=0;\n    int last_index=-1;\n    for (int i = 0; i < n; ++i)\n    {\n        array_sum+=a[i];\n        if (sum<0)\n        {\n            sum=0;\n            if (a[i]>=0)\n            {\n                last_index=i;\n            }\n        }\n        sum+=a[i];\n    }\n\n    if (array_sum<0)\n    {\n        return -1;\n    }\n    return last_index;\n}\n

\n\n

复杂度：O(n)

\n