This can be done by kadanes algo..
//suppose n numbers has been stored in array
// i is the intial point
// n is the number of points to be considered in O(n)
int maxsum(int a[], int N,int i,int n)
{
int max=0;
int max_end_ here =0;
int max_so_far=0;
for(int j=i;j<N;j++)
{
if(j==N)
{ j=0;
N=n-(N-i);
}
if(max<a[j])
max=a[j];
}
if(max>0) // // check Is there any positive value or not....if not then
return max value..could be least negative number
{
for(int j=i;j<N;j++) //
{
if(j==N)
{ j=0;
N=n-(N-i);
}
max_end_ here= max_end_ here+a[j];
if(max_end_ here<0)
max_end_ here=0;
if(max_so_far<max_end_ here)
max_so_far= max_end_ here
}
}
else
{ max_so_far=max; // return max value..could be least negative number
}
return (max_so_far);
}
With regards,
Praveen Raj
DCE-IT
9999735993
[email protected]
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
