求C++中最小和邻接子数组的起止索引

Question

我正试图找到最小和邻接子数组的起始和结束索引。我试了很多次，但还是找不到。为此我使用C++。

求最小和邻接子数组的代码：

#include <bits/stdc++.h> 
using namespace std; 
int main() 
{ 
    int arr[] = {3, -4, 2, -3, -1, 7, -5}; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    int min_ending_here = INT_MAX;  
    int min_so_far = INT_MAX; 
    for (int i=0; i<n; i++) 
    { 
        if (min_ending_here > 0) 
            min_ending_here = arr[i]; 

        else
            min_ending_here += arr[i]; 

        min_so_far = min(min_so_far, min_ending_here);           
    } 
    cout<<"minimum sum = "<<min_so_far; 
}

Answer 1

假设存在多个子数组，其和值最小，则取起始索引值最小的子数组，我们可以将上述解决方案修改如下：

#include <bits/stdc++.h>
using namespace std;
int main() {
   int arr[] = {3, -4, 2, -3, -1, 7, -5};
   int n = sizeof(arr) / sizeof(arr[0]);
   int min_ending_here = INT_MAX;
   int min_so_far = INT_MAX;
   int last_idx = 0; // indication of fresh start of contiguous summation
   int start_idx; // for holding start index
   int end_idx; // for holding end index
   for (int i=0; i<n; i++) {
      if (min_ending_here > 0) {
          min_ending_here = arr[i];
          last_idx = i;
      }
      else {
          min_ending_here += arr[i];
      }
      if (min_so_far > min_ending_here) {
          min_so_far = min_ending_here;
          start_idx = last_idx;
          end_idx = i;
      }
  }
  cout<<"minimum sum = "<<min_so_far<<endl;
  cout<<"start index = "<<start_idx<<endl;
  cout<<"end index = "<<end_idx<<endl;
}