Kadane's Algorithm finds the Sub-Array of any size with Maximum sum.
for example of Array is like
| 1 | -2 | 3 | 4 | -10 | 6 |
then sub-array will be
| 3 | 4 |
ALGORITHM
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;
}
print(A,n,i,j,*pk,*pl,s,t);
}
return s;
}