Max Sum

hdu1003:http://acm.hdu.edu.cn/showproblem.php?pid=1003

题意：给你n个数的序列，求一个连续最大的子序列的和。
题解：简单的动态规划。从开始，选择一个连续和是递增的序列，如果当前这段和小于零.则从下一段开始，若下一段的和大于该段，则更新起点和终点。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 int a[100020];
 7 int n,cas;
 8 int main(){
 9     scanf("%d",&cas);
10     int t=1;
11     while(cas--){
12         scanf("%d",&n);
13         memset(a,0,sizeof(a));
14         for(int i=1;i<=n;i++)
15             scanf("%d",&a[i]);
16         int sum=-100000000,maxn=0;
17         int l=1,r=1,st=1;
18         for(int i=1;i<=n;i++){
19             maxn+=a[i];
20             if(maxn>sum){
21               sum=maxn;r=i;l=st;    
22               }
23             if(maxn<0){
24                maxn=0;st=i+1;
25              } 
26          }
27         if(t>1)
28         printf("
");
29         printf("Case %d:
",t++);
30         printf("%d %d %d
",sum,l,r);    
31      }
32 }

View Code