@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.
