MAX —sum 好久前做过 但是再看到的时候觉得的有点陌生
设Si是一定以i结尾的最大连续子序列
S1=a[1]；
Sn=Sn-1>=0?Sn-1+a[n]:a[n];//状态转移大致是这样 则S1 —Sn中必有所求子序列 边存边比较 答案就出来了
#include<stdio.h>
int main()
{
int a,P,n,start,temp,max,end,sum,mark=0;
scanf("%d",&P);
while(P--)
{
max=-1000,temp=1,sum =0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a);
sum+=a;
if(sum>max)
{
max=sum;
start=temp;
end=i;
}
if(sum<0)
{
sum=0;
temp=i+1;
}
}
printf("Case %d:\n%d %d %d\n",++mark,max,start,end);
if(P!=0){
printf("\n");
}
}
return 0;
}
原文：http://www.cnblogs.com/Geek-xiyang/p/5157056.html