[HDOJ1231]最大连续子序列

混了好几个地方的博客，还是觉得博客园比较靠谱，于是决定在这里安家落户了。本人本科生一个，希望各位巨巨多多指教~

　　Hello World!

单独一个象征性的问候实在是太low了，还是决定来点实质性的。。。比如水个题什么的。

希望能交到更多朋友~

---------------------------------------------------------------------------------------------------------------------------------------------------------------

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1231

给定K个整数的序列{ N1, N2, ..., NK }，其任意连续子序列可表示为{ Ni, Ni+1, ...,
Nj }，其中 1 <= i <= j <= K。最大连续子序列是所有连续子序列中元素和最大的一个，
例如给定序列{ -2, 11, -4, 13, -5, -2 }，其最大连续子序列为{ 11, -4, 13 }，最大和
为20。
在今年的数据结构考卷中，要求编写程序得到最大和，现在增加一个要求，即还需要输出该
子序列的第一个和最后一个元素。

水题就要水着做，此题花式AC，现提供蛋疼方法如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 int main()
 5 {
 6     int i, k, n, arr[10000];
 7     int l, r, maxSum, thisSum, rflag, lflag, zflag, pflag, pos;
 8     while(scanf("%d", &n) != EOF && n)
 9     {
10         k = 0;
11         pos = 0;
12         maxSum = 0;
13         thisSum = 0;
14         rflag = 0;
15         pflag = 0;
16         zflag = 0;
17         for(i = 0; i < n; i++)
18         {
19             scanf("%d", &arr[i]);
20             if(arr[i] == 0)
21             {
22                 zflag = 1;
23             }
24             if(arr[i] > 0)
25             {
26                 pos = pos + 1;
27                 pflag = 1;
28             }
29         }
30         r = arr[0];
31         l = arr[0];
32         for(i = 0; i < n; i++)
33         {
34             thisSum += arr[i];
35             if(rflag)        
36             {
37                 r = arr[i-1];
38             }
39             rflag = 0;
40             if(thisSum > maxSum)
41             {
42                 maxSum = thisSum;
43                 rflag = 1;
44                 lflag = 1;
45             }
46             else if(thisSum < 0)
47             {
48                 k = i + 1;
49                 thisSum = 0;
50                 lflag = 0;
51             }
52             if(lflag)
53             {
54                 l = arr[k];
55             }
56         }
57         if(zflag && !pos)
58         {
59             printf("%d %d %d
", 0, 0, 0);
60             continue;
61         }
62         if(!pflag)
63         {
64             printf("%d %d %d
", 0, arr[0], arr[n-1]);
65             continue;
66         }
67         else
68         {
69             printf("%d %d %d
", maxSum, l, r);
70         }
71     }
72     return 0;
73 }

正确ac姿势：

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <iomanip>
 4 #include <cstring>
 5 #include <climits>
 6 #include <complex>
 7 #include <fstream>
 8 #include <cassert>
 9 #include <cstdio>
10 #include <bitset>
11 #include <vector>
12 #include <deque>
13 #include <queue>
14 #include <stack>
15 #include <ctime>
16 #include <set>
17 #include <map>
18 #include <cmath>
19 
20 using namespace std;
21 
22 const int maxn = 10010;
23 int a[maxn];
24 int n;
25 
26 int main() {
27     // freopen("in", "r", stdin);
28     while(~scanf("%d", &n) && n) {
29         for(int i = 0; i < n; i++) {
30             scanf("%d", &a[i]);
31         }
32         int mx = -1;
33         int cr = 0;
34         int tp = 0;
35         int bg;
36         int ed;
37         for(int i = 0; i < n; i++) {
38             cr += a[i];
39             if(cr > mx) {
40                 mx = cr;
41                 bg = tp;
42                 ed = i;
43             }
44             if(cr < 0) {
45                 cr = 0;
46                 tp = i + 1;
47             }
48         }
49         if(mx < 0) {
50             printf("%d %d %d
", 0, a[0], a[n-1]);
51         }
52         else {
53             printf("%d %d %d
", mx, a[bg], a[ed]);
54         }
55     }
56 }