Kadane's Algorithm

For Finding Maximum Sub-Array of Any Size

Kadane algorithm has several versions for finding of maximum sub array.  Its 1-D version is O(n) while the 2D verions is in O(N^3).

/*

Finds the Sub-Array of any size with Maximum sum.

INPUT

           A===>Array In which SubArray To Find

           n===>Size of Array

           pk===>Pointer to k which give lower index of sub-array

           pl===>Pointer to l which give upper index of sub-array

Returns the sum of sub-array

*/

int Kadane(int* A,int n,int* pk,int* pl)
{
         *pk=0;
         *pl=0;
         int s=1<<31;
         int t=0;
         int i,j=0;
        for(i=0;i<n;i++)
        {
                 t=t+A[i];
                if(t>s)
               {
                       *pk=j;
                       *pl=i;
                       s=t;
               }
               if(t<0)
              {
                    t=0;
                    j=i+1;
              }
        }
        return s;
}