Maximum Subarray Problem (Kadane's Algorithm)

This is an interesting problem in all interviews. 

This algorithm is for the array with negative numbers and zero because the maximum subarray sum for the array with all positive numbers is sum of all array elements. So, do expect an array with negative numbers and zeroes. 

What is Subarray? 

It can be defined in either of the following way:

• Arrays inside another array
• Elements inside an array which only contains contiguous elements.

For example, for the given array {1, 2, 3}, the subarrays can be {1}, {2}, {3}, {1, 2}, {2, 3}, {1, 2, 3}. 

Find the Leetcode problem statement here. 

All the programs has a way to be solved by traditional Bruteforce approach, but the efficient approach is Kadane's algorithm as we are reducing the computation of few subarrays. 

Kadane Algorithm is one of the dynamic programming approach. 

Run the code here to debug or explore further.

#include <iostream>

using namespace std;

int max_subarray_sum(int element[], int N)
{
   int MaxSum = element[0], Sum = 0;
   int startIndex = 0, endIndex = 0;
   for (int i = 0; i < N; i++) { 
       Sum = max (element[i], Sum + element[i]);
       //cout << "i " << i << " a[i] " << a[i] << " sumEach " << sumEach << endl;
       if (MaxSum < Sum) {
           MaxSum = Sum;
           
           if (element[i] == Sum) {
               startIndex = i;
               // There can also be only one number as a subarray
               endIndex = i;
           } else {
               endIndex = i;
           }
          // cout << "i " << i << " a[i] " << a[i] << " sumEach " << sumEach << " maxSum " << maxSum << endl;
       }

   }
   cout << "The maximum subarray sum " << MaxSum << " index starts at "<< startIndex << " ends at " << endIndex << endl;
   return MaxSum;
}

int main()
{
   /*
    * Input : {-2, -9, 5, 0, -1, 8, -2, -3, -4, -1, 0, 3} => sum 12, start 2, end 5
    * Input : {-2, -9, 5, 8, -2, -3, -4, -1, 0, 3} => sum 13, start 2, end 3
    * Input : {-2, -9, 5, 8, 0, -2, -3, -4, -1, 0, 3} => sum 13, start 2, end 3 
    *         Explanation: considering 0 has no effect
    * Input : {-2, -9, 5, 8, 0, 2, -2, -3, -4, -1, 0, 3} => sum 15, start 2, end 5
    * Input : {-2, -9, 0, 5, 8, -2, -3, -4, -1, 0, 3} => sum 12, start 2, end 5
    * Input : {-2, -9, 5, 0, -1, 8, -2, -3, -4, -1, 0, 3} => sum 12, start 2, end 5
    * Input : {-2, -9, -5, 0, -1, -8, -2, -3, -4, -1, 0, -3} => sum 0, start 3, end 3
    * Input : {-2, -9, -5, -1, -8, -2, -3, -4, -1, -3} => sum -1, start 3, end 3
    * Input : {2, 9, 5, 5, 8, 2, 3, 4, 1, 3} => sum 42, start 0, end 9
    * Input : {-2, 1, -3, 4, -1, 2, 1, -5, 4} => sum 6, start 3, end 6
    */
   int a[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
   /*
    * The below is the only way to get array length 
    * sizeof(a) is 40 here (Eg: 10(number of elements) * 4(integer size))
    */
   int n = sizeof(a)/sizeof(a[0]);
   int sum = max_subarray_sum(a, n);
   //cout << "The maximum subarray sum is " << sum << endl;
   return 0;
}

The simplified algorithm of the same above program:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int len = nums.size();
        int maxSum = nums[0], sum = 0;
        
        for (int i = 0; i < len; i++) {
            sum = max(sum + nums[i], nums[i]);
            maxSum = max(sum, maxSum); 
        }
        return maxSum;
    }
};

The variable sum decides if the current element needs to be added into the sub array or not. 

The variable maxSum tracks the maximum sum of the sub array. 

This is one of the dynamic programming.