题目
Problem Description
Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14.
Input
The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).
Output
For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.
Sample Input
2 5 6 -1 5 4 -7 7 0 6 -1 1 -6 7 -5
Sample Output
Case 1: 14 1 4 Case 2: 7 1 6
分析
动规最大子段和问题，比较模板
代码
1 /********************** 2 User:Mandy.H.Y 3 Language:c++ 4 Problem:hdu max sum 5 Algorithm: 6 Scores: 7 **********************/ 8 //hdu与poj都不能用万能头文件 9 //#include<bits/stdc++.h> 10 #include<cstdio> 11 #include<iomanip> 12 #include<algorithm> 13 #include<cmath> 14 15 using namespace std; 16 17 const int maxn = 1e5 + 5; 18 19 int t,n,ans,ansl,ansr; 20 int a[maxn]; 21 int l[maxn],r[maxn],sum[maxn]; 22 23 template<class T>inline void read(T &x){ 24 x = 0;bool flag = 0;char ch = getchar(); 25 while(!isdigit(ch)) flag |= ch == '-',ch = getchar(); 26 while(isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48),ch = getchar(); 27 if(flag) x = -x; 28 } 29 30 template<class T>void putch(const T x){ 31 if(x > 9) putch(x / 10); 32 putchar(x % 10 | 48); 33 } 34 35 template<class T>void put(const T x){ 36 if(x < 0) putchar('-'),putch(-x); 37 else putch(x); 38 } 39 40 void readdata(){ 41 read(n); 42 for(int i = 1;i <= n; ++ i) read(a[i]); 43 } 44 45 void work(int j){ 46 ans = -2e9; 47 sum[0] = -1;//初始化 48 for(int i = 1;i <= n;++ i){ 49 l[i] = i;r[i] = i; 50 if(sum[i - 1] >= 0){//要输出第一个位置，需要sum[0]初始化为负 51 sum[i] = sum[i - 1] + a[i]; 52 l[i] = l[i - 1]; 53 }else sum[i] = a[i]; 54 55 if(ans < sum[i]){//要输出第一个位置 56 ans = sum[i]; 57 ansl = l[i]; 58 ansr = r[i]; 59 } 60 } 61 62 printf("Case %d: ",j); 63 put(ans);putchar(' '); 64 put(ansl);putchar(' '); 65 put(ansr); 66 puts("");//一个空格和换行符引发的血案 67 if(j != t) puts("");//要空行 68 } 69 70 int main(){ 71 read(t); 72 for(int i = 1;i <= t; ++ i){ 73 readdata(); 74 work(i); 75 } 76 return 0; 77 }