Maximum subarray problem

Template:Wikify is deprecated. Please use a more specific cleanup template as listed in the documentation.

 ??? 

Kandane'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;
}

External links

• Kandane's Algorithm