Apr 19, 2011

find maximum sum of a sub arrary

void maxsumsubarray(int a[], int n)
{
int sum=0;
int maxsofar = 0;
int start =0;
int end=0;
int count =0;
for(int i=0;i< n;i++)
{
if(maxsofar + a[i] > 0)
{
maxsofar += a[i];
count++;
}
else
{
maxsofar = 0;
count =0;
}

if(sum < maxsofar)
{
sum = maxsofar;
end = i;
start = end - count + 1;
}
}
cout << "maxsum = " << sum ;
cout << " start = a[" << start << "] = " << a[start] << " end = a[" << end << "] = " << a[end] << endl;
}

No comments: