2.
#include <algorithm>
#include <iostream>
using namespace std;
int n,a[1005] ;
struct Node
{
int h, j, m, w;
Node (const int _h, const int _j, const int _m, const int _w) :
h (_h) , j (_j) , m (_m) ,w (_w)
{}
Node operator+ (const Node &o) const
{
return Node(
max(h,w+o.h) ,
max(max (j,o.j) ,m +o.h) ,
max(m+o.w,o.m) ,
w+o.w) ;
}
} ;
Node solve1 (int h,int m)
{
if (h>m)
return Node (-1, -1, -1, -1) ;
if (h==m)
return Node(max(a[h], 0) , max(a[h], 0) , max(a[h], 0) ,a[h]) ;
int j= (h + m) >> 1;
return solve1 (h, j) + solve1(j+1, m);
}
int solve2 (int h, int m)
{
if (h>m)
return -1;
if (h==m)
return max(a[h], 0) ;
int j= (h+m) >> 1;
int wh=0,wm =0;
int wht=0,wmt=0;
for (int i = j; i >= h; i--) {
wht +=a[i] ;
wh =max(wh,wht) ;
}
for (int i = j+1; i <= m; i++){
wmt +=a[i] ;
wm=max(wm,wmt) ;
}
return max (max(solve2(h, j), solve2(j+1,m)) ,wh + wm) ;
}
int main ( )
{
cin >> n;
for (int i=1; i <= n; i++) cin >> a[i];
cout << solve1(1, n).j << endl;
cout << solve2(1, n) << endl;
return 0;
}
假设输入的所有数的绝对值都不超过1000,完成下面的判断题和单选题：
判断题
1) 程序总是会正常执行并输出两行两个相等的数。( )
2) 第28行与第38行分别有可能执行两次及以上。( )
3) 当输入为“5-10 11-95-7”时，输出的第二行为“7”。( )
选择题
4) solve1(1, n)的时间复杂度为( )。
5) solve2 (1,n) 的时间复杂度为（）。
6) 当输入为“10 -3 2 10 0 -8 9 -4 -5 9 4”时，输出的第一行为( )。