Kadane’s Algorithm (The Maximum Subarray Problem)

Download the code here: [wpdm_package id=’1301′]

Given an array of numbers, to find the subarray which gives the maximum sum can be solved using Kadane’s algorithm. The array may contain both positive and negative numbers.

We have 2 variables max_so_far to find the maximum sum so far in the array and max_ending_here to find the sum of elements till each index. Both of them are first initialized to the starting element of the array. We also have 3 variables begin, begin_temp and end to keep in track of the starting and ending position of the sub array.The algorithm basically consists of 3 conditions:

    1. if max_ending_here is a negative number at an index i, then the new max_ending_here is assigned to the element at that position. Also, the begin_temp is made to point to index i;
    2. if the above condition does not satisfy then we add the element at position i to max_ending here.
    3. whenever max_so_far becomes lesser than max_ending_here, we assign begin_temp to begin, and the new end becomes the index i. This is continued till last element. The code is as shown:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{ vector array;
int n,a;
cout<<"Enter the length of the array:";
cin>>n;
while(n--)
{ cin>>a;
array.push_back(a); //inserting each element into the vector
}
int max_so_far=array[0], max_ending_here=array[0];
int begin=0; //begin, begin_temp and end are 3 variables for keeping track of the start and end of the sub array
int begin_temp=0;
int end=0;
for(int i=0;i<array.size();i++)
{ if(max_ending_here<0) //if max_ending_here is a -ve no, we assign array[i] to it and the new begin_temp will be the position i { max_ending_here=array[i]; begin_temp=i; } else { max_ending_here+=array[i]; //else we calculate max_ending_here by adding each element one by one to get the max sum. } if(max_ending_here>max_so_far)
  { max_so_far=max_ending_here; //when max_so_far becomes less than max_ending_here, we will make max_ending here as the new max_so_far
begin=begin_temp; //begin will be assigned begin_temp
end=i; //end will be the index i
}
}
cout<<"\nThe max subarray is:\n";
for(int i=begin;i<=end;i++)
{ cout<<array[i]<<" ";
}
cout<<endl;
}

Leave a Reply

Your email address will not be published. Required fields are marked *