太久没做题了，手都生了不少，所以从比较简单的题目开始做起。先上题目
Max Sum
Time Limit: 2000/1000 MS
(Java/Others) Memory Limit: 65536/32768 K
(Java/Others)
Total Submission(s): 123917 Accepted
Submission(s): 28659
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
这一题的解题方法有很多种，而且这一题并不是第一次见到，只是做了好几次都做不出来(好吧，我承认自己不太会DP=
=)这一题的方法可以用DP，可以用分治，一开始的做法我都是用分治，结果一直wa,然后现在换成了DP的解法，由于DP不是很懂，所以韩看了一下别人的解法=
=。
解法是这样的：我们要求最大的一段数字的和，那么我们从一个方向入手，向另一个方向扫描，并记录一段当前可能是最大值得序列的其实和末尾；如果这个当前最大值比总体的最大值还要大，那么就用这个当前的最大值代替总体的最大值，如果当前最大值加上第i个数以后比以前还要小，那么就从第i个位置开始算起作为当前最大值。总之感觉描述有点模糊，毕竟还是不太了解，详细看代码。
1 #include <cstdio> 2 #include <cstring> 3 #define MAX 100001 4 using namespace std; 5 6 int a[MAX]; 7 int n; 8 9 int main() 10 { 11 int t,pos,st,ed,maxn,sum; 12 scanf("%d",&t); 13 for(int i=1;i<=t;i++){ 14 scanf("%d",&n); 15 for(int j=0;j<n;j++){ 16 scanf("%d",&a[j]); 17 } 18 ed=st=pos=0; 19 maxn=sum=a[0]; 20 for(int j=1;j<n;j++){ 21 if(sum+a[j]<a[j]){ //加上当前位置的数以后最大值会变小，或者是前面的当前最大值是负数 22 pos=j; 23 sum=a[j]; 24 }else{ //序列还在上升，所以暂定最大值继续累加。 25 sum+=a[j]; 26 } 27 if(sum>maxn){ //判定暂定的最大值是不是全体最大值，如果是就将全体最大值替换 28 maxn=sum; 29 st=pos; 30 ed=j; 31 } 32 } 33 printf("Case %d:\n%d %d %d\n",i,maxn,st+1,ed+1); 34 if(i!=t) printf("\n"); 35 } 36 return 0; 37 }