```
1     #include <algorithm>
2     #include <iostream>
3     using namespace std;
4 
5     int n, a[1005];
6 
7     struct Node
8     {
9         int h, j, m, w;
10
11        Node(const int _h, const int _j, const int _m, const int _w):
12        h(_h), j(_j), m(_m), w(_w)
13        { }
14
15        Node operator+(const Node &o) const
16        {
17            return Node(
18            max(h, w + o.h),
19            max(max(j, o.j), m + o.h),
20            max(m + o.w, o.m),
21            w + o.w);
22        }
23    };
24
25    Node solve1(int h, int m)
26    {
27        if (h > m)
28            return Node(-1, -1, -1, -1);
29        if (h == m)
30            return Node(max(a[h], 0), max(a[h], 0), max(a[h], 0), a[h]);
31        int j = (h + m) >> 1;
32        return solve1(h, j) + solve1(j + 1, m);
33    }
34
35    int solve2(int h, int m)
36    {
37        if (h > m)
38            return -1;
39        if (h == m)
40            return max(a[h], 0);
41        int j = (h + m) >> 1;
42        int wh = 0, wm = 0;
43        int wht = 0, wmt = 0;
44        for (int i = j; i >= h; i--) {
45            wht += a[i];
46            wh = max(wh, wht);
47        }
48        for (int i = j + 1; i <= m; i++) {
49            wmt += a[i];
50            wm = max(wm, wmt);
51        }
52        return max(max(solve2(h, j), solve2(j + 1, m)), wh + wm);
53    }
54
55    int main()
56    {
57        cin >> n;
58        for (int i = 1; i <= n; i++) cin >> a[i];
59        cout << solve1(1, n).j << endl;
60        cout << solve2(1, n) << endl;
61        return 0;
62    }
```

假设输入的所有数的绝对值都不超过1000 ，完成下面的判断题和单选题：
	判断题
1. 程序总是会正常执行并输出两行两个相等的数。（）
2. 第 28 行与第 38 行分别有可能执行两次及以上。（）
3. 当输入为“5 -10 11 -9 5 -7”时，输出的第二行为“7”。（）
	单选题
4. solve1(1, n) 的时间复杂度为（）。
5. solve2(1, n) 的时间复杂度为（）。
6. 当输入为“10 -3 2 10 0 -8 9 -4 -5 9 4”时，输出的第一行为（ ）。
    1. A.正确    B.错误
    2. A.正确    B.错误
    3. A.正确    B.错误
    4. A. O(log n)    B. O(n)    C. O(n log n)   D. O(n2)
    5. A. O(log n)    B. O(n)    C. O(n log n)   D. O(n2)
    6. A.”13”    B.”17”    C.”24”    D.”12”


有道小图灵信息学

2021CSP提高级第一轮认证

有道小图灵 信息学

2021CSP提高级第一轮认证

有道小图灵信息学