hdu 1003 hdu 1231 最大连续子序列【dp】

题意自明。可能是真的进步了点，记得刚开始研究这个问题时还想了好长时间，hdu 1231还手推了很长时间，今天重新写干净利落就AC了。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 using namespace std;
 6 const int MAXN=1e5+50;
 7 int a[MAXN];
 8 
 9 int main()
10 {
11     int T,N;
12     scanf("%d",&T);
13     for(int cas=1;cas<=T;cas++)
14     {
15         scanf("%d",&N);
16         for(int i=1;i<=N;i++){
17             scanf("%d",&a[i]);
18         }
19         int ans=-1e9;
20         int l=1,r=1,pos=1;
21         int tot=0;
22         for(int i=1;i<=N;i++){
23             tot+=a[i];
24             if(tot>ans){
25                 ans=tot;
26                 r=i;
27                 l=pos;
28             }
29             if(tot<0){
30                 tot=0;
31                 pos=i+1;
32             }
33         }
34         printf("Case %d:
%d %d %d
",cas,ans,l,r);
35         if(cas!=T)
36             printf("
");
37     }
38     return 0;
39 }

HDU 1003

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 using namespace std;
 6 const int MAXN=1e5+50;
 7 int a[MAXN];
 8 int N;
 9 
10 int main()
11 {
12     while(scanf("%d",&N)==1,N)
13     {
14         int cnt=0;
15         for(int i=1;i<=N;i++){
16             scanf("%d",&a[i]);
17             if(a[i]<0) cnt++;
18         }
19         int ans=-1e9;
20         int l=1,r=1,pos=1;
21         int tot=0;
22         for(int i=1;i<=N;i++){
23             tot+=a[i];
24             if(tot>ans){
25                 ans=tot;
26                 r=i;
27                 l=pos;
28             }
29             if(tot<0){
30                 tot=0;
31                 pos=i+1;
32             }
33         }
34         if(cnt==N){
35             ans=0;
36             printf("%d %d %d
",ans,a[1],a[N]);
37         }else{
38             printf("%d %d %d
",ans,a[l],a[r]);
39         }
40     }
41     return 0;
42 }

HDU 1231