Wednesday 8 August 2012

Find the subset of an array having maximum sum

#include<iostream.h>
#include<conio.h>
void main()
{
      clrscr();
      int a[]={1,3,-8,2,-1,10,-2,1};
      int n=sizeof(a)/sizeof(int);
      int sum=a[0];
      int max=-1;
      int start,end,s=0,e=0;
      for(int i=1;i<n;i++)
      {
            if(sum>=max)
            {
                  start=s;
                  end=e;
                  max=sum;
            }
            if(sum<0)
            {
                  s=e=i;
                  sum=a[i];
                  continue;
            }
            sum+=a[i];
            e=i;
      }
      cout<<max;
      getch();
}


No comments:

Post a Comment