0

合計が 0 になる任意のサイズ N の整数の配列 a[] (たとえば、a[] = {-1, 0, 5, 3, -9, 2}) が与えられた場合、インデックス i ($0 \le i\le N-1$) 各部分和 $S_j = \sum_{k=i}^ j a_{k\pmod N}$ ($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);
}

しかし、私の最初の質問では、ループが許可されており、インデックスを見つける必要があります。したがって、2 つの問題には少なくとも 2 つの違いがあります。

(おっと、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 に答える