最大サブアレイヒントが必要

Question

最大合計を持つ配列（少なくとも1つの を含む）内の連続したサブアレイを検索します。

たとえば、配列[-2,1、-3,4、-1,2,1、-5,4]が与えられた場合、隣接するサブ配列[4、-1,2,1]には、連続する 最大合計= 6

私はこの問題を解決できませんが、ですが、私はちょっとしたヒントが好きです。

これはダイナミックプログラミングを使用して解決できると言われていますが、接続を確認するのには苦労しています。

アレイの合計がDP接続になるかどうかを確認します。

Answer 1

max; 
max_ele; 
for (i=0; i< i++) { 
    if (i ==0) { 
    max_ele = i; 
    max =a[i]; 

} else if (max < max + a[i]) { 
    max - max + a[i]; 
    max_ele = i; 
} else { 
    max = 0; 
} 
} 

you get max_ele after this iteration, trace back till negative element or first element to get max. 

Answer 2

hereを参照してください。

あなたはこのようなものになり、このような場合、解決するためにKadaneのアルゴリズムを使用する必要があります。

Initialize: 
    max_so_far = 0 
    max_ending_here = 0 

Loop for each element of the array 
    (a) max_ending_here = max_ending_here + a[i] 
    (b) if(max_ending_here < 0) 
     max_ending_here = 0 
    (c) if(max_so_far < max_ending_here) 
     max_so_far = max_ending_here 
    return max_so_far 

ご参照用のサンプル・コード：

static int maxSubArraySum(int a[]) 
{ 
    int size = a.length; 
    int max_so_far = Integer.MIN_VALUE, max_ending_here = 0; 

    for (int i = 0; i < size; i++) 
    { 
     max_ending_here = max_ending_here + a[i]; 
     if (max_so_far < max_ending_here) 
      max_so_far = max_ending_here; 
     if (max_ending_here < 0) 
      max_ending_here = 0; 
    } 
    return max_so_far; 
}