Subj : Re: question about finding sum of subset of contiguos elements o
To   : comp.programming
From : maadhuu
Date : Thu Oct 06 2005 10:49 pm

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;   
}

.