题意：给出一列数，求其中的最大子段和以及该子段的开头和结尾位置。
因为刚学过DP没几天，所以还会这题，我开了一个 dp[100002][2]，其中 dp[i][0] 记录以 i 为结尾的最大子段的和， dp[i][1] 记录以第 i 个数 A[i] 为结尾的和最大子段的开始位置。
对于每一个数 A[i] ：
我考察它的前一个数 A[i-1] ，若以 A[i-1] 为结尾的最大子段和 dp[i-1][0] 大于等于 0 ，那么在这个基础上加上 A[i] ，一定大于等于 A[i] 本身，所以以第 i 个数结尾的最大子段就是以第 i-1 个数结尾的最大子段加上第 i 个数，以此更新 dp[i] ；
而若 dp[i-1][0] 小于 0 ，那么在这个子段的基础上加上 A[i] ，一定小于 A[i] 本身，所以以第 i 个数为结尾的和最大子段就是这个数本身，所以 dp[i] 也就可以这样得到了。
当遍历一遍数列之后，再求最大的 dp[i][0] ，输出 dp[i][0] 、 dp[i][1] 和 i 即可。
1 #include<stdio.h>
2 int A[100002];
3 long long dp[100002][2];
4 int main(){
5 int T;
6 while(scanf("%d",&T)!=EOF){
7 long long N,q;
8 for(q=1;q<=T;q++){
9 scanf("%I64d",&N);
10 long long i,ans,stx,edx=1;
11 for(i=1;i<=N;i++)scanf("%d",&A[i]);
12 printf("Case %I64d:
",q);
13 ans=dp[1][0]=A[1];
14 stx=dp[1][1]=1;
15 for(i=2;i<=N;i++){
16 if(dp[i-1][0]>=0){
17 dp[i][0]=dp[i-1][0]+A[i];
18 dp[i][1]=dp[i-1][1];
19 }
20 else{
21 dp[i][0]=A[i];
22 dp[i][1]=i;
23 }
24 }
25 for(i=1;i<=N;i++){
26 if(dp[i][0]>ans){
27 ans=dp[i][0];
28 stx=dp[i][1];
29 edx=i;
30 }
31 }
32 printf("%I64d %I64d %I64d
",ans,stx,edx);
33 if(q!=T)printf("
");
34 }
35 }
36 return 0;
37 }