nyoj 子串喝

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<string>
 6 #include<queue>
 7 #include<algorithm>
 8 #include<map>
 9 #include<iomanip>
10 #include<climits>
11 #include<string.h>
12 #include<cmath>
13 #include<stdlib.h>
14 #include<vector>
15 #include<stack>
16 #include<set>
17 #define INF 1e7
18 #define MAXN 100010
19 #define maxn 1000010
20 #define Mod 1000007
21 #define N 1010
22 using namespace std;
23 typedef long long LL;
24 
25 int T;
26 int num[1000100];
27 
28 void run()
29 {
30     int len;
31     int sum = 0, st,beg = 1,en, flag = -1111111;
32     scanf("%d",&len);
33     for (int i = 1; i <= len; ++i)
34         scanf("%d", &num[i]);
35     for (int i = 1; i <= len; ++i) {
36         sum += num[i];
37         if (sum > flag) {
38             en = i;
39             st = beg;
40             flag = sum;
41         }
42         if (sum < 0) {
43             beg = i + 1;
44             sum = 0;
45         }
46     }
47     cout << flag << endl;
48 }
49 
50 int main()
51 {
52     scanf("%d",&T);
53     while (T--)
54         run();
55     //system("pause");
56     return 0;
57 }