インデックスを持つ配列の最大部分配列を見つける

Question

整数の配列内で最大部分配列S(h,k)を探したいと思います。私はすでに最大値を見つけるためのコード（Javaで）を持っていますが、それはうまくいきますが、どのようにしてhとkの2つのインデックスを得ることができますか？

int []a = {-2, 1, -3, 4, -1, 2, 1, -5, 4 }; 
int max_so_far = 0, max_ending_here = 0; 
for(int i=0; i<a.length; i++) { 
    max_ending_here = Math.max(0, max_ending_here + a[i]); 
    max_so_far = Math.max(max_so_far, max_ending_here); 
} 
System.out.println("The maximal sum of subsequence is = "+max_so_far)"; 

Answer 1

あなたはmax_so_farを改善した時に最後のインデックスを格納し、後ろから順に "解明" でサブシーケンス自体を取得することができます：

int []a = {-2, 1, -3, 4, -1, 2, 1, -5, 4 }; 
int max_so_far = 0, max_ending_here = 0, index_max = 0; 
for(int i=0; i<a.length; i++) { 
    max_ending_here = Math.max(0, max_ending_here + a[i]); 
    if (max_so_far < max_ending_here) { 
     max_so_far = max_ending_here; 
     index_max = i; 
    } 
} 
System.out.print("The maximal sum of subsequence is = "+max_so_far); 
int j = index_max; 
while (j >= 0 && max_so_far > 0) { 
    max_so_far -= a[j--]; 
} 
System.out.println(", from = "+(j+1)+" to "+index_max+", inclusive"); 

Demo.

注：マーカーを使用して背中から解くことは、動的プログラミングアルゴリズムの共通のテーマです。単純なケースでは、index_maxは、max_so_farを0に戻すインデックスを後方から見ている特別なマーカーの役割を果たします。

Answer 2

ありがとうShreyas Sarvothamaおよびdasblinkenligh tは答えです。 Utsav Chokshiによってgeeksforgeeks.orgのウェブサイトに書かれたこのコードの良い解決策を発見しました。

解決策は以下のとおりです。

int []a = {-2, 1, -3, 4, -1, 2, 1, -5, 4 }; 
int max_so_far = a[0], max_ending_here = a[0]; 
int curStartIndex = 0; 
int maxStartIndex = 0; 
int maxEndIndex = 0; 

for(int i=1; i<a.length; i++) { 
     max_ending_here = Math.max(a[i], max_ending_here + a[i]); 
     if(max_ending_here > max_so_far){ 
      max_so_far = max_ending_here; 
      maxStartIndex = curStartIndex; 
      maxEndIndex = i; 
     } 
     if(max_ending_here < 0){ 
      curStartIndex = i+1; 
     } 
}