思路

恰好两个不重合非空连续子段，全负数不能返回0；线性双状态或前后缀。

参考程序（C++11）

#include <bits/stdc++.h>
using namespace std;
int main(){int t;cin>>t;while(t--){int n;cin>>n;vector<long long>a(n),l(n),r(n);for(auto &x:a)cin>>x;long long v=a[0];l[0]=v;for(int i=1;i<n;i++){v=max(a[i],v+a[i]);l[i]=max(l[i-1],v);}v=a[n-1];r[n-1]=v;for(int i=n-2;i>=0;i--){v=max(a[i],v+a[i]);r[i]=max(r[i+1],v);}long long ans=LLONG_MIN;for(int i=0;i+1<n;i++)ans=max(ans,l[i]+r[i+1]);cout<<ans<<'\n';}}