プログラムの実行時間をΘnにする方法

Question

入力は-5から5の範囲の整数に設定されます。その結果、整数の最長のサブセットが得られます。ゼロ以上。

私は以下を考え出すことができる： 入力が[N 0]入力される

let start, longestStart, end, longestEnd, sum = 0 

for i=0 to n-1 
start = i 
sum = input[i] 
    for j=1 to n 
    if sum + input[j] >= 0 then 
    end=j; 
    if end - start > longestEnd - longestStart then 
    longestStart = start; 
    longestEnd = end; 

をしかし、これはΘ（N^2）です。私はこのループになっΘ（n）の は、我々は数字の配列にこれを適用することができ、任意のA、Bまたはnの

a - b == (a + n) - (b + n) 

ので、あなたに

Answer 1

ありがとうを作る方法が何であるかを知りたいのですがすべての要素の合計を0から現在まで維持します。上の方程式から、インデックスaからbまでのサブアレイの和はsum（要素0-b） - sum（要素0-a）です。

ローカルミニマムとマキシマ、およびそれらの合計を追跡することで、1回のパスで最大範囲のサブアレイ、つまりO（n）を見つけることができます。