1

我试图找到最小总和连续子数组的开始和结束索引。我尝试了很多次，但我无法找到。我为此使用 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; 
}

输出：minimum sum = -6

4

2 回答 2

4

假设如果存在多个具有最小总和的连续子数组，我们将采用具有最小起始索引的子数组，我们可以将上述解决方案修改如下：

#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;
}
于 2018-11-21T09:45:25.407 回答
1

我用 2 个数组（当前（结果为 [1,4]）和注释（结果为 [3,3]）对其进行了测试，见代码）：

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

    int infimum = INT_MAX; // hold minimum value.
    std::pair<int, int> idx(-1, -1); // subarray's indexes 

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

        // indexes addition
        if( min_so_far == min_ending_here)
        {
            infimum = min(arr[i], infimum);
            if( infimum == arr[i] )
            {
                idx.first = i;
            }
            idx.second = i;
        }
        // << indexes addition

    } 
    cout<<"minimum sum = "<<min_so_far << " indexes: " << idx.first << " " << idx.second; 
}
于 2018-11-21T07:15:22.990 回答