Subj : Re: question about finding sum of subset of contiguos elements o
To   : comp.programming
From : Googmeister
Date : Fri Oct 07 2005 03:34 pm


maadhuu wrote:
> hello ,
>
> This was an interview Question and one possible O(n) solution I was
> thinking of is this : Is there any error in this ?? I tried it out for a
> few arbitrary cases .
>
> int maxsubset(int *a[],int size )
> {
>       int j = 0;
>       int sum = 0;//some value which is sure to be less
>       int max = -999;
>       int start = 0 , end =0;
>       int i = 0;
>       while( j < size)
>       {
>           sum += a[j];
>           if( sum > max)
>           {
>                  max = sum ;
>                  start = i;
>                  end = j;
>           }
>           else if(sum < 0)
>           {
>                  i = j+1 ; //this is the case when i have lost hope with
> that particular sub sequence
>           }
>            j=j+1;
>        }
>        return max;
> }

Well, for starters, it doesn't work for the input { -2, 1 }
since you never reset sum. It doesn't work for the input { -1 }
either.

.