Kadane’s Algorithm – Maximum Sum Subarray

The given task in this problem is that we have to find the series of contiguous elements with the maximum sum in any given array. You can find the problem here which is based on this algorithm.

Before jumping to the Kadane’s algorithm, we will look the naive solution of this problem, and then we will see its efficient using Kadane’s algorithm.

Naive solution – Maximum Sum Subarray

So, problem here is to find a subarray of maximum sum within the array. To find it, we should find all the possible subarrays and by brute-force approach, we start with first element then finding all possible subarrays beginning with it then for second element, again finding all possible subarrays with it and so on.

int solve(int arr[], int n){

  int max_sum = arr[0];

  for(int i=0; i<n; i++){
    int curr_sum = 0;

    for(int j =i; j<n; j++){
      curr_sum += arr[j];
      max_sum = max(max_sum,curr_sum);
    }
  }
  return max_sum;
}

So, the above function has 2 argument the array itself and its length. First we initialize a variable for MAXIMUM SUM and pass it value of first element. We then start iterating from the first element, we will be finding every subarray starting with this. And declaring a variable for the sum of this very loop called CURRENT SUM. Time complexity for this code is O(n²). So, we will be trying to minimize the time complexity to O(n).

Kadane’s Algorithm – Maximum Sum Subarray

What are the different approach you will try? Can we try sorting? We will find the first positive number and every further element to end, it will give maximum sum. But, wait we want the subarrays. Sorting will distort the sequence. It is out of the options then. Can we use space then?The answer is Yes. By using Kaden’s algorithm, we can find maximum sum subarray.

int maxSubArraySum(int arr[], int n)
{
    // stores the maximum sum subarray found so far
    int res = a[0]; 

    // stores the maximum sum of subarray ending at the current position
    int max_Ending = a[0];

    //traverse the array
    for (int i = 1; i < n; i++)
    {
        //update the current sum
        max_Ending = max(max_Ending + a[i], a[i]);

        //update the maximum sum if greater
        res = max(max_Ending, res);

    }
    return res;
}

Above function has same arguments, here we are initializing same number of variables, but the approach here is to compare simultaneously and discard the sequence if have any element which decrease the sum. The key difference in this algorithm is that we are trying to maintain the positive sum ending sequence. This can be seen as simple example of Dynamic Programming.

Visit: Best Technology Website

Let us take a dry run of this program, we will passing array as {-3, 8, -2, 4, -5, 6} and since length is 6, n=6.

At start res = -3, max_Ending= -3

i=1, max_Ending = max(-3 + 8, 8)= 8, res= 8

i=2, max_Ending = max(8 + (-2), -2)= 6, res= 8

i=3, max_Ending = max(6 + 4, 4)= 10, res= 10

i=4, max_Ending = max(10 + (-5), -5)= 5, res= 10

i=5, max_Ending = max(5 + 6, 6)= 11, res= 11

So, the function will return the value 11 and that’s our answer. Subsequence array having max sum is {8, -2, 4, -5, 6} with sum 11.