Posted on 2008-06-04 16:10
superman 閱讀(768)
評論(0) 編輯 收藏 引用 所屬分類:
POJ
1 /* Accepted 1008K 579MS G++ 1655B */
2 #include <iostream>
3
4 using namespace std;
5
6 const int maxn = 50000;
7
8 int main()
9 {
10 int n, m;
11 int x[maxn + 1];
12 int l[maxn + 1], r[maxn + 1];
13
14 scanf("%d", &m);
15 while(m--)
16 {
17 scanf("%d", &n);
18 bool AllNegative = true;
19 for(int i = 1; i <= n; i++)
20 {
21 scanf("%d", x + i);
22 if(x[i] > 0)
23 AllNegative = false;
24 }
25 if(n == 2)
26 {
27 cout << x[1] + x[2] << endl; continue;
28 }
29 if(AllNegative)
30 {
31 int max = INT_MIN, a, b;
32 for(int i = 1; i <= n; i++)
33 if(x[i] > max)
34 {
35 max = x[i];
36 a = i;
37 }
38 max = INT_MIN;
39 for(int i = 1; i <= n; i++)
40 if(x[i] > max && i != a)
41 {
42 max = x[i];
43 b = i;
44 }
45 cout << x[a] + x[b] << endl;
46 continue;
47 }
48
49 int max, sum;
50
51 max = sum = 0;
52 for(int i = 1; i <= n; i++)
53 {
54 sum += x[i];
55 max >?= sum;
56 sum >?= 0;
57 l[i] = max;
58 }
59
60 max = sum = 0;
61 for(int i = n; i >= 1; i--)
62 {
63 sum += x[i];
64 max >?= sum;
65 sum >?= 0;
66 r[i] = max;
67 }
68
69 int ans = 0;
70 for(int i = 1; i <= n - 1; i++)
71 ans >?= (l[i] + r[i + 1]);
72
73 printf("%d\n", ans);
74 }
75
76 return 0;
77 }
78