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; ilen*2; i++)
{
if(max_till_now + a[i%len] 0)
max_till_now =0;
else
max_till_now += a[i%len];
if(max_sum
seems to be a independent problemu can see maximum subarray problem
On Tue, Nov 1, 2011 at 11:54 PM, atul007 atul.87fri...@gmail.com wrote:
Assume that there are n numbers (some possibly negative) on a circle,
and
we wish to find the maximum contiguous sum along an arc of the circle.
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;jN;j++)
{
@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
Assume that there are n numbers (some possibly negative) on a circle,
and
we wish to find the maximum contiguous sum along an arc of the circle.
Give an
efficient algorithm for solving this problem.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks
