Найти начальный и конечный индекс непрерывной подмассивы наименьшей суммы в 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; 
}

Выход: minimum sum = -6

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

Answer 2

Я протестировал его с 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; 
}