最大の和を持つ配列内の部分配列を探します。

Question

最大和を持つ配列内の部分配列（が少なくとも2つの数字が）を探します。 たとえば、配列[-2、-1、-3、-4、-1]を指定すると、 連続する部分配列[-2、-1]は最大の合計= -3を持ちます。入力サイズ（N）のアレイのための 公共INT maxSubArray（INT [] NUMSに）{}

Answer 1

それを解決する方法のストリームである場合、O（N）時間 フォローアップでそれを行うために 試み。別の配列Bを作成して、Farのように合計を格納することができます。 親の配列をたどります。

int max = Integer.MIN; 
B[0] = A[0]; 
    for(i=1;i<A.length;i++) 
    { 
    if(A[i] > 0){ 
    B[i]=B[i-1] + A[i]; 
    }else if(A[i]+B[i-1] > max){ 
    B[i] = A[i]+B[i-1] 
    max = A[i]+B[i-1] 
    } 
    else{ 
    B[i] = A[i]; 
    } 

は今アレイBでの最大数は、連続したサブアレイの最大の可能な合計を持っていますが、サブアレイを知りません。

Answer 2

Kadane's Algorithmを変更して使用することができます。

あなたはKadaneのアルゴリズムhereを見つけることができます。 （サブアレイの端も保存します）。

どうすれば変更できますか？

- >ちょうどあなたが> = 1

すなわちRIGHT-LEFTを取っているウィンドウサイズのトラックに保つ私は、これは、負を含む数字のすべてのセットのために役立つはずだと思います。

まだすべての負の数（O（n）を確認できます）。ループをからNまで：最大= max（arr [i] + arr [i + 1]、最大）; ケースが覆われているかどうかを確認するだけです。このような

Answer 3

何かが動作するはずです：

int maxvalue = int.MIN_VALUE; 
for (int i = 0; i < N; i++) 
    for (int j = i + 1; j < N; j++) { 
    int value = 0; 
    for (int x = i; x <= j; x++) 
     value += array[x]; 
    if (value > maxvalue) 
     maxvalue = value; 
    } 
return maxvalue;