hdu1003 Max Sum---最大子段和+记录开始结束点

题目链接：

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

题目大意：

求最大子段和，并且输出最大子段和的起始位置和终止位置。

思路：

根据最大子段和基本方法，直接在线处理（如果对最大子段和不熟悉，点这里）

需要增加两个变量，start和finish，记录最大子段和的起点和终点。如果thissum > maxsum,更新这三个值。如果thissum < 0,设置thissum = 0，并且thisstart = i + 1,因为thissum<0时包括了第i个数字，可推出第i个数一定是负数，那thisstart肯定要先设置成下一个i。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<string>
 6 using namespace std;
 7 typedef long long ll;
 8 const int INF = 1<<30;
 9 int T, cases;
10 int n;
11 int main()
12 {
13     cin >> T;
14     while(T--)
15     {
16         cin >> n;
17         int thissum = 0, maxsum = -INF, start = 1, finish = 1, x;
18         int thisstart = 1;
19         for(int i = 1; i <= n; i++)
20         {
21             cin >> x;
22             thissum += x;
23             if(thissum > maxsum)
24             {
25                 maxsum = thissum;
26                 start = thisstart;
27                 finish = i;
28             }
29             if(thissum < 0)
30             {
31                 thissum = 0;
32                 thisstart = i + 1;
33             }
34         }
35         printf("Case %d:
", ++cases);
36         printf("%d %d %d
", maxsum, start, finish);
37         if(T)cout<<endl;
38     }
39     return 0;
40 }