[algogeeks] Re: Given an array containing both positive and negative integers, we r required to find the sub-array with the largest sum

[Arvind Sharma]

This will not work when you have a negative number in the resultant subarray.

If n=3 and a={ 7, -4,  25}.

Returns 25,2,2 while the correct answer is 28,0,2

Your algo assumes that if the current element is negative it cannot appear in the final list. Correct?
Regards,

Arvind.

 

On 1/21/06, algorithm <[EMAIL PROTECTED] > wrote:

Here is my  code :- //O(n) complexity

void largest_subarray(int* a, int n, int* sum, int *start_index, int*
end_index)
{
   int maxX=0, maxY=0, maxsum=a[0];
   int tmpX=0,tmpY=0,tmpsum=a[0];
   int i;

   for (i=1; i<n; i++)
   {
      if (tmpsum > 0 && a[i] > 0)
      {
       tmpY = i;
       tmpsum += a[i];
      }
      else
      {
       tmpX = tmpY = i;
       tmpsum = a[i];
      }

      if (tmpsum > maxsum)
      {
         maxsum = tmpsum;
         maxX = tmpX;
         maxY = tmpY;
      }
   }
   *start_index = maxX;
   *end_index = maxY;
   *sum = maxsum;
}