0

给定一个任意大小的整数数组 a[]，其总和为 0（例如，a[] = {-1, 0, 5, 3, -9, 2}），是否总是存在索引 i（$0 \le i\le N-1$) 使得每个部分和 $S_j = \sum_{k=i}^ j a_{k\pmod N}$ (with $N+i-1\ge j\ge i$ ) 是非负数吗？

在示例中 a[] = {-1, 0, 5, 3, -9, 2} 其中 $a_0 = -1, a_1 = 0, ... a_5 = 2$ （我们可以检查 $\sum_{ k=0}^{5} a_k=0$)，我们可以从 $i=5$ 开始，使得部分和 $2, 2-1, 2-1+0, 2-1+0+5, 2- 1+0+5+3, 2-1+0+5+3-9$ 都是非负数。

如果我们可以证明这样的索引 $i$ 总是存在的，那么找到索引 $i$ 的有效算法是什么？有一个明显的 $O(N^2)$ 算法，但我们可以在 $O(N)$ 中做到吗？谢谢。

注意：这个问题有点类似于另一个问题：给定一个整数数组 $a_0,a_1,a_2,...,a_n$（他们不必加起来等于 0），找到 $\max_{0\le i\le j\le n}\sum_{k=i}^j a_k$。这可以在时间 $O(n)$ 中解决，如下所示：

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);
}

但在我最初的问题中，我们可以循环，我们需要找到索引。所以这两个问题之间至少有两个不同之处。

（哎呀，LaTeX 在这个网站上不起作用......这就是为什么有那些美元符号 $ 浮动......）

这是我在数学论坛上的问题：

https://math.stackexchange.com/questions/539923/finding-the-index-such-that-all-partial-sums-are-nonnegative

4

1 回答 1

0

代码价值一千字。它应该是正确的。我实际上并没有运行并检查。

c代码：

int getTheIndex(int* a,int length){
 int min=a[0];
 int mini=0;
 int sum=a[0];
 for(int t=1;t<length;t++){
  sum+=a[t];
  if(min<sum){
   min=sum;
   mini=t;
  }
 }
 return mini;
}
于 2013-10-26T03:42:20.263 回答