找到一個索引，使所有部分和是非負的

Question

給定一個數組a []的任意大小爲N的整數，其總和爲0（例如a [] = { - 1,0，5，3，-9， 2}），是否總是存在一個索引i（$ 0 \ lei \ 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); 
} 

但在我原來的問題，我們被允許環路周圍，而我們需要找到索引。所以這兩個問題至少有兩點不同。

（哎呀，乳膠不會在這個網站的工作......這就是爲什麼有這些錢的跡象$左右浮動...）

這是我在數學論壇的問題：

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

Answer 1

代碼千言萬語。 它應該是正確的。我沒有真正運行和檢查。

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