Maximum Subarray Problem

Maximum subarray problem can be solved in multiple ways. Here we will look at some of the approaches.

Approach 1:  Brute Force

In case of brute force we will be finding all the possible subarrays and comparing their sizes to find out the maximum sum subarray.
 

void MaxSumSubArray( int * a, int size) {     int MaxSum = a[0];     int MaxSumStart = 0, MaxSumEnd = 0;     for( int i = 1; i < size; i++)     {         int tempSum = 0;         int j = i;         while(j>=0)         {             tempSum += a[j];             if ( tempSum > MaxSum )             {                 MaxSum = tempSum;                 MaxSumStart = j;                 MaxSumEnd = i;             }             j--;         }     }     cout << "Max Sum in the array : " << MaxSum << endl;     cout << "Maz Sum Start : " << MaxSumStart << "  MaxSumEnd : " << MaxSumEnd << endl; }

Approach 2:

We can modify the brute force algorithm in order to use the existing max subarray to find out next maximum subarray as given below.

void MaxSumSubArray( int * a, int size) {     int MaxSum = a[0];     int MaxSumStart = 0, MaxSumEnd = 0;     for( int i = 1; i < size; i++)     {         int tempSum = 0;         int j = i;         int tempStart = MaxSumStart;         while(j>=tempStart)         {             tempSum += a[j];             if ( tempSum > MaxSum )             {                 MaxSum = tempSum;                 MaxSumStart = j;                 MaxSumEnd = i;             }             j--;         }     }     cout << "Max Sum in the array : " << MaxSum << endl;     cout << "Maz Sum Start : " << MaxSumStart << "  MaxSumEnd : " << MaxSumEnd << endl; }

Approach 3: Kadane's algorithm

This approach uses simple mechanism, just go on adding the numbers in the sum till the time sum is greater than zero, but maintain the maximum sum found till the time. This is C++ variation of Kadane's algorithm.

void MaximumSubArraySum(vector<int> input) {     if (input.size() > 0)     {         int sum = 0;         int MaxSum = 0;         int start = 0;         int end = 0;         for (int i = 0; i < input.size(); i++)         {             sum += input[i];             if (sum > 0)             {                 if (sum > MaxSum)                 {                     MaxSum = sum;                     end = i;                 }             }             else             {                 sum = 0;                 start = i;             }         }         cout << "Max Sum : " << MaxSum << " sub Array : " << start + 1 << " - " << end << endl;     } }