撰写 t1 t2
d(A) = max{ ∑ai + ∑aj | 1 <= s1 <= t1 < s2 <= t2 <= n }
i=s1 j=s2
题意：给出一段长度为n的整数序列，求d(A)，也就是求最大不相交的两段子序列和，两个子序列各自内连续。
题解：dp,或者应该说是贪心
- 与最大连续子序列和一样的做法，将前面的序列都看作一个数
- 这样当这个数小等于0时，我们舍弃它，ans归零。
- 当这个数大于0时，我们接受它，ans+f[i]。
- 每个操作我们都将ans与maxx比较，得出最大值
- 但是问题来了，两段怎么办？
- 其实也很简单，只要开一个F[i]数组代表以i结尾的最大值，开G[i]数组代表以i开头的最大值
- 正扫一遍得出F[i],反扫一遍得出G[i]
- 最后1~n-1中取出F[i]+G[i+1]的最大值即可
//#include<bits/stdc++.h>
#include<algorithm>
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define P(a,b,c) make_pair(a,make_pair(b,c))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define CLR(vis) memset(vis,0,sizeof(vis))
#define MST(vis,pos) memset(vis,pos,sizeof(vis))
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1000000007;
const int INF = 0x3f3f3f3f;
ll gcd(ll a, ll b) {
return b ? gcd(b, a%b) : a;
}
template<class T>inline void gmax(T &A, T B){
(A<B)&&(A=B);//if(B>A)A=B;
}
template<class T>inline void gmin(T &A, T B){
(A>B)&&(A=B);//if(B<A)A=B;
}
template <class T>
inline bool scan_d(T &ret) {
char c;
int sgn;
if(c=getchar(),c==EOF) return 0; //EOF
while(c!='-'&&(c<'0'||c>'9')) c=getchar();
sgn=(c=='-')?-1:1;
ret=(c=='-')?0:(c-'0');
while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');
ret*=sgn;
return 1;
}
inline void outt(int x) {
if(x>9) outt(x/10);
putchar(x%10+'0');
}
const int maxn=5e5+10;
int a[maxn];
int f[maxn];
int F[maxn];
int g[maxn];
int G[maxn];
int maxx;
int main(){
ios::sync_with_stdio( false );
int t,n;
scan_d(t);
while(t--){
scan_d(n);
rep(i,1,n)scan_d(a[i]);
maxx=F[1]=f[1]=a[1];
//正反扫一遍还可以知道子序列和最大的范围
rep(i,2,n){
f[i]=a[i]+max(f[i-1],0);//可以理解为贪心，将前面的值加起来不为负的值看作一个数
maxx=F[i]=max(f[i],maxx);//F[i]代表以i结尾的子序列和的最大值
}
maxx=G[n]=g[n]=a[n];
per(i,1,n-1){
g[i]=a[i]+max(g[i+1],0);
maxx=G[i]=max(g[i],maxx);//G[i]表示以i开头的子序列和的最大值
}
maxx=F[1]+G[2];
rep(i,2,n-1){
if(F[i]+G[i+1]>maxx)maxx=F[i]+G[i+1];
}
cout<<maxx<<endl;
}
return 0;
}