(数据结构)最大子列算法

发表于

给定整数序列A1,A2,....,An(可能有负数),求其最大的子序列的和值(为方便起见,如果所有的整数都为负数,则最大子列的和为0)例如:
输入为:-2,11,-4,13,-5,-2时,其和值为20
请给出以线性时间运行的求解算法.

#include<stdio.h>
#define n 30
int main()
{
int a[]={0,1,-2,4,8,-10,5,9,-2,4,0,1,-2,4,8,-10,-25,9,-2,4,0,1,-2,4,8,-10,5,9,-2,-2};
int max=0,maxnow=0,now=0,i,tag=0,a1=0,a2=0;
for(i=0;i<n;i++)
{
if(tag==0)
{
if(a<=0) continue;
if(a>0)
{
tag=1;
a1=i;
maxnow=a;
}
}
if(tag==1)
{
now+=a;
if(now>maxnow) a2=i;
maxnow=(now>maxnow)?now:maxnow;
if(now<0)
{
tag=0;
maxnow=0;
}
}
max=(max>maxnow)?max:maxnow;
}
printf("the max sum(%d):",max);
for(i=a1;i<=a2;i++)
printf("%d ",a);
return 0;
}