hdu 1231（最大连续子序列）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1231
dp水题；
View Code
 1 #include<iostream>
 2 #include<cstring>
 3 const int N=11000;
 4 using namespace std;
 5 int a[N],dp[N];
 6 
 7 int main(){
 8     int n;
 9     while(scanf("%d",&n)!=EOF&&n){
10         memset(dp,0,sizeof(dp));
11         memset(a,0,sizeof(a));
12         int count=0;
13         for(int i=0;i<n;i++){
14             scanf("%d",&a[i]);
15             if(a[i]<0)count++;
16         }
17         if(count==n){
18             printf("0 %d %d\n",a[0],a[n-1]);
19         }else {
20             dp[0]=a[0];
21             for(int i=1;i<n;i++){
22                 dp[i]=max(dp[i-1]+a[i],a[i]);
23             }
24             int k=0,l=0,h=0;
25             for(int i=1;i<n;i++){
26                 if(dp[i]>dp[h])h=i;
27             }
28             int sum=0;
29             for(k=h;k>=0;k--){
30                 sum+=a[k];
31                 if(sum==dp[h]){
32                     l=k;
33                     break;
34                 }
35             }
36             printf("%d %d %d\n",dp[h],a[l],a[h]);
37         }
38     }
39     return 0;
40 }