题意：给定n个数，求两段连续不重叠子段的最大和。

思路非常easy。把原串划为两段。求两段的连续最大子串和之和，这里要先预处理一下，用lmax数组表示1到i的最大连续子串和，用rmax数组表示n到i的最大连续子串和，这样将时间复杂度降为O（n）。

#include<cstdio>

#include<cstring>

#include<cmath>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#include<vector>

#include<map>

#include<queue>

#include<stack>

#include<string>

#include<map>

#include<set>

#define eps 1e-6

#define LL long long

using namespace std;  

const int maxn = 50000 + 50;

const int INF = 0x3f3f3f3f;

int n, a[maxn], lmax[maxn], rmax[maxn];

void init() {

	cin >> n;

	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);

	int enda = a[1];

	lmax[1] = a[1];

	for(int i = 2; i <= n; i++) {

		enda = max(enda+a[i], a[i]);

		lmax[i] = max(lmax[i-1], enda);

	}

	enda = a[n];

	rmax[n] = a[n];

	for(int i = n-1; i >= 1; i--) {

		enda = max(enda+a[i], a[i]);

		rmax[i] = max(rmax[i+1], enda);

	}

}

void solve() {

	int ans = -INF;

	for(int i = 1; i < n; i++) ans = max(ans, lmax[i]+rmax[i+1]);

	cout << ans << endl;

}

int main() {

	//freopen("input.txt", "r", stdin);

	int t; cin >> t;

	while(t--) {

		init();

		solve();

	}

	return 0;

}