Dynamic programming -Maximum sum contiguous sub-array

LOGIC HEAP

ARTICLE CONTRIBUTED BY : Snehil Rastogi ( IIT Roorkee )

NAME: Kadane Algorithm

TYPE: Dynamic Programming

Explanation: Kadane Algorithm is used to find the maximum sum of the contiguous subarray in a given array containing    at least one element.

1.  The naive approach to solve the problem (as discussed in previous video) takes O(n^3) as it considers each sub array then it fixes element in that sub array one by one and then calculates the sum and compare.

2.       Using Divide and Conquer - this approach divides the array into two halves and then recurses over each half and calculates the sum + another module to calculate sum if maximum lies in part of both sub arrays.

 Algorithm -

maxsubarraysum(int a[], int l , int h)
{
    if(l==h)
    return a[l];
    int m = l+(h-l)/2;
 
    /* recurses on left and right subarrays and max sum if subarray crosses the mid point */
 
    maxsum = max(maxsubarraysum(a,l,m), maxsubarraysum(a,m+1,h), maxinboth(a,l,m,h));
     /* data type of maxsum(here int ) same as type of array */
 
    return maxsum;
}

maxinboth(int a[], int l , int m , int h)
{
    int sum=0;
    int lsum = INT_MIN;
    for(i=m;i>=l;i--)
    {
        sum+=a[i];
        if(lsum<sum)
        lsum = sum;
    }
 
    int rsum = INT_MIN;
    sum=0;
    for(i=m+1; i<=h;i++)
    {
        if(rsum<sum)
        rsum=sum;
    }
    return lsum+rsum;
}

Time Complexity = 2T(n/2)+O(n) = O(nlogn)

3.       Dynamic Programming Approach - The array is traversed only once.

Two variables currmax (hold the current maximum for each element of the array) and totalmax ( holding the   total maximum encountered so far , at the end it holds the answer to the maximum sum found)

        

Apart from these the variables index, maxsindex ( holding the starting index of the subarray whose sum is largest),    maxeindex (holding the ending index of the subarray whose sum is largest) holds the values for the indices.

The algorithm is –

Maxsubarraysum(int a[], int n)   // the entered array and its size
currmax = a[0], toalmax=a[0];
index =0, maxsindex =0, maxeindex =0;    // initially the starting value and starting index

// now traverse the remaining array

for( i=1 to n)

/*check  maximum among current a[i] and  current max + a[i]  – this step holds its importance if negative numbers are present  in the array , if only positive numbers are present in the array then the comparison
currmax +=a[i]
if(currmax < 0)  currmax=0;
would suffice
but with negative numbers present this won’t work(obviously) */

if( a[i] > currmax+a[i])
currmax = a[i];
index =i ;         //for holding the index intermediately element wise

else
currmax = currmax+a[i];

// now compare with overall total encountered so far

If(totalmax < currmax)
totalmax = currmax;
maxsindex = index;
maxeindex = i;

print (totalmax , maxsindex , maxeindex)

Time Complexity – as we are traversing the array only once so O(n) , much less then the naïve approach and better then the divide and conquer strategy discussed .

Uses & Applications –

This is a very important algorithm and quite easy to understand. It is often asked in the interview questions.

Extensions –

1.       Finding maximum sum in square sub matrix from a 2-D array.

2.       Finding maximum sum in circular sub array

3.       Finding maximum product  in a sub array (the approach is exactly same with just one simple change)

Problems to try on –

1.       http://www.codechef.com/problems/DELISH

2.       http://www.codechef.com/problems/SWEET

3.       http://www.spoj.com/problems/HOTELS/

These are some of the simplest and direct applications of the Kadane algorithm. Do go and try these for the better understanding of the algorithm. 

KADANE'S Algorithm for minimum/ maximum sum on a contiguous subarray having both positive and negative values

 #include <iostream>

#include<bits/stdc++.h>
using namespace std;
void maxSubArraySum(int a[], int n)
{
    int i;
    int currmax = a[0];                 //holding the maximum for each index
    int  totalmax = a[0];               //holding the overall maximum(answer) for the specific sub array
  
    // starting and ending indices of the subarray whose sum is maximum
  
    int index =0, maxsindex=0,maxeindex=0;
    for(i=1 ; i<n; i++)
    {
        // as negative numbers are also present in the array so comparison with a[i] is essential
        if(a[i] >= currmax + a[i])
        {
          
            currmax = a[i];
            index=i;
        }
        else
        currmax = currmax + a[i];
      
        if(currmax >= totalmax)
        {
            totalmax = currmax;
            maxsindex = index;                         // update the indices
            maxeindex=i;
        }
    }
    printf("%dt%dt%dn",totalmax,maxsindex,maxeindex);
  
}

/* same as maxSubArraySum() , only comparison opeartor reversed as we are now checking for minimum in a contiguous sub array
*/
void minSubArraySum(int a[], int n)
{
  
    int currmin=a[0], totalmin=a[0],index=0, minsindex=0, mineindex=0, i;
    for(i=1; i<n; i++)
    {
        if(a[i]<=currmin+a[i])
        {
            currmin=a[i];
            index=i;
        }
        else
        currmin= currmin+a[i];
      
        if(totalmin>currmin)
        {
            totalmin=currmin;
            minsindex=index;
            mineindex=i;
        }
    }
    printf("%dt%dt%dn",totalmin,minsindex,mineindex);
}


int main() {
  
    int a[] =  {6, 3, 10, 0, -12, 3 , -11, -10};
    int n = sizeof(a)/sizeof(a[0]);
  
    maxSubArraySum(a, n);
    minSubArraySum(a,n);
    return 0;
}