題目：http://acm.hdu.edu.cn/showproblem.php?pid=1003
算法思想：
設(shè)S[j]為以a[j]結(jié)尾的子序列最大的和，那么，
S[1]=a[1];
S[j]=S[j-1]>=0?S[j-1]+a[j]:a[j];
那么要求的連續(xù)子序列中有最大和的就是S[1],S[2],......,S[n]中最大的。
算法設(shè)計(jì)：
1 int a[100001];
2 int s[100001];
3 int n,str,end;
4
5 int DPMaxSum(int n)
6 {
7 int max;
8 int restr;
9 str=restr=1;
10 end=1;
11 max=s[1]=a[1];
12
13 for(int i=2;i<=n;i++)
14 {
15 if(s[i-1]>=0)
16 {
17 s[i]=s[i-1]+a[i];
18 }
19 else
20 {
21 s[i]=a[i];
22 restr=i;
23 }
24 if(max<=s[i])
25 {
26 max=s[i];
27 str=restr;
28 end=i;
29 }
30 }
31 return max;
32 }
33
優(yōu)化：求S[i]只依賴于前一個(gè)S[i-1]和a[i],所以還可以優(yōu)化算法。
1 #include<stdio.h>
2 int i,cas,j,k,t,max,s,e,n,x;
3 main()
4 {
5 while(scanf("%d",&cas)!=EOF)
6 {
7 for(i=0;i<cas;i++)
8 {
9 if(i)printf("\n");
10 printf("Case %d:\n",i+1);
11 scanf("%d",&n);
12 max=-99;
13 for(j=k=1,t=0;j<=n;j++)
14 {
15 scanf("%d",&x);
16 t+=x;
17 if(t>max) {max=t;s=k;e=j;}
18 if(t<0) {k=j+1;t=0;}
19 }
20 printf("%d %d %d\n",max,s,e);
21 }
22 }
23 }
24