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.


           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)
         int s=1<<31;
         int t=0;
         int i,j=0;
        return s;