iterate it twice the length
max_sub_array()
{
int a[] = {200 -10 -10 -10 -10 -10 100} ;
int len = sizeof(a) / sizeof(a[0]);
int max_sum =0;
int max_till_now =0;
for(int i=0; i<len*2; i++)
{
if(max_till_now + a[i%len] < 0)
max_till_now =0;
else
max_till_now += a[i%len];
if(max_sum < max_till_now)
max_sum = max_till_now
}
return max_sum;
}
surender
On Wed, Nov 2, 2011 at 10:13 PM, atul anand <[email protected]> wrote:
> @praveen : thats the tricky part of this question .... bcoz it is a
> circle , this algo will fail...
>
> *[200 -10 -10 -10 -10 -10 100] *for this input , answer should be 300
> (200+100).
>
> but simple kadane algorithmn will not give the desired output
>
> On Wed, Nov 2, 2011 at 4:14 PM, praveen raj <[email protected]> wrote:
>
>> 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.
>>
>
> --
> 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.
>
--
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.
