Main BLOGGER
Google
WWW THIS BLOG
Friday, April 01, 2005
 
Maximum Sum in Integer Array
Consider an array of integers a[1] ... a[n]. Design an O(n) algorithm that finds the pair I,J (with I <= J) such that the sum is maximized. (Note that integers can be both positive and negative.)



enum {N=10};
int a[N]={31,-41,59,26,-53,58,97,-93,-23,84};
int maxsofar = 0;
int maxhere = 0;
int lmIndex = 0;
int rmIndex = 0;
for (int i=0;i {
if(maxhere+a[i]>0)
{
maxhere = maxhere+a[i];
}else
{
maxhere=0;
lmIndex = i+1;
}

if (maxhere>maxsofar)
{
maxsofar=maxhere;
rmIndex=i;
}
}
printf("a[%d]--a[%d]=%d\n",lmIndex,rmIndex, maxsofar);


This works on the fact that once temp falls below 0 , we can drop it.



<< Home

Powered by Blogger

Google
WWW THIS BLOG