CODEWITHSUNDEEP
c++kadanes-algorithm
Vishal Srivastav
Vishal Srivastav

Reputation: 603

Find the starting and ending index of smallest sum contiguous subarray in C++

I am trying to find the starting and ending index of the smallest sum contiguous sub-array. I tried many times but I could not able to find. I am using C++ for this.

Code for finding Smallest sum contiguous sub-array :

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

Output: minimum sum = -6

Upvotes: 1

Views: 1242

Answers (2)

BishalG
BishalG

Reputation: 1424

Assuming that if there exists multiple contiguous sub-arrays with minimum sum we will take the one with minimum starting index, we may modify above solution as below: 

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

Upvotes: 4

Alexander Chernin
Alexander Chernin

Reputation: 444

I tested it with 2 arrays (current ( the result is [1,4]) and commented (the result is [3,3]), see the code):

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

Upvotes: 1

Related Questions