HDU 1231 最大连续子序列

 1 //#define LOCAL
 2 #include <iostream>
 3 #include <cstdio>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 const int maxn = 10000 + 10;
 8 int a[maxn];
 9 
10 struct Node
11 {
12     int w;
13     int l, r;
14 }node[maxn];
15 
16 int main(void)
17 {
18     #ifdef LOCAL
19         freopen("1231in.txt", "r", stdin);
20     #endif
21 
22     int n;
23     while(scanf("%d", &n) && n)
24     {
25         int i;
26         bool flag = true;
27         for(i = 1; i <= n; ++i)
28         {
29             scanf("%d", &a[i]);
30             if(a[i] >= 0)    flag = false;
31             node[i].w = a[i];
32             node[i].l = node[i].r = i;
33         }
34 
35         for(i = 2; i <= n; ++i)
36         {
37             if(node[i-1].w+a[i] >= node[i].w)
38             {
39                 node[i].w = node[i-1].w + a[i];
40                 node[i].l = node[i-1].l;
41             }
42         }
43 
44         if(flag)
45         {
46             printf("0 %d %d\n", a[1], a[n]);
47             continue;
48         }
49 
50         int ans = 1;
51         for(i = 2; i <= n; ++i)
52             if(node[i].w > node[ans].w)
53                 ans = i;
54         printf("%d %d %d\n", node[ans].w, a[node[ans].l], a[node[ans].r]);
55     }
56     return 0;
57 }