最大の連続したサブシーケンスの合計の始まりと終わりを見つける

Question

これは、最大の連続する最大のサブシーケンスの合計を見つけるためのプログラムです。私はsum.Howを計算することができますこのコードは、この最大サブシーケンスの合計の開始と終了のインデックスを見つけるために変更することができますか？

int maxSubArraySum(int a[], int size) 
{ 
    int final_max = 0, curr_max = 0; 
    for (int i = 0; i < size; i++) 
    { 
     curr_max = curr_max + a[i]; 
     if (curr_max < 0) 
      curr_max = 0; 

     else if (final_max < curr_max) 
      final_max = curr_max; 
    } 
    return final_max; 
} 

Answer 1

合計を開始するインデックスと合計が終了するインデックスを覚えておく必要があります。

struct SumAndRange{ 
    int sum; 
    int start; 
    int stop; 
    SumAndRange() : sum(0),start(0),stop(0) {} 
}; 

SumAndRange maxSubArraySum(int a[], int size) { 
    SumAndRange curr;    // we will start with the sum of the first element 
    SumAndRange final; 
    for (int i = 0; i < size; i++) { 
     curr.sum = curr.sum + a[i]; 
     if (curr.sum < 0) {   // if we reset the sum it will 
      curr.sum = 0;   // start with the next index 
      curr.start = i+1;  
      curr.stop = i+1;   // ...and we also handle the case of 
            // the sum is only one element 

     } else {      // otherwise the sum continues with 
      curr.stop = i;   // this index 
      if (final.sum < curr.sum) { final = curr; } 
     } 
    } 
    return final; 
} 

int main() { 
    int a[] = { 2,-6,7,-3,12}; 
    SumAndRange sar = maxSubArraySum(a,5); 
    std::cout << sar.sum << " " << sar.start << " " << sar.stop << std::endl; 
    return 0; 
}