查找最大連續子序列總和的開始和結尾

Question

這是我的程序，用於查找最大最大連續子序列總和。我能夠計算總和。如何修改這段代碼以找到這個最大子序列和的開始和結束索引？

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; 
}