2479
2593

这两题所要求的是一样 只是输入不太一样而已

思路：
其实这题算是求一个序列的最大子段和的一个拓展延伸
对于最大子段和 我们知道dp[i]=max(dp[i-1]+a[i],a[i]) 表示以i结尾的最大子段和
那么这题所要求的是要两个不相交的
所以我们考虑 开两个数组l,r 分别维护正序和倒序的最大子段和

处理完之后，注意我们要的是不相交即可 ，也就是第一个区间的右端点和第二个区间的左端点中间可以相隔很多距离，所以我们在去对两个数组进行更新
l[i]=max(l[i],l[i-1])
r[i]=max(r[i],r[i+1])
这样子扫一遍之后的意思就变为l[i]表示i左边的最大子段和 r[i]表示i右边的最大子段和
最后遍历一遍求最大即可

#include<stdio.h>
using namespace std;
typedef long long ll;
int a[50005],l[50005],r[50005];
int main(){

    int n,t;
    scanf("%d",&t);
    while(t--){
       scanf("%d",&n);
       for(int i=1;i<=n;i++){
          scanf("%d",a+i);
          if(i==1) l[i]=a[i];
          else l[i]=max(l[i-1]+a[i],a[i]);
       }
       for(int i=n;i;i--){
           if(i==n) r[i]=a[i];
           else r[i]=max(r[i+1]+a[i],a[i]);       
       }
       for(int i=2;i<=n;i++) l[i]=max(l[i],l[i-1]);
       for(int i=n-1;i;i--) r[i]=max(r[i],r[i+1]);
       int ma=-2e9;
       for(int i=1;i<n;i++) ma=max(ma,l[i]+r[i+1]);
       printf("%d\n",ma);
    }
    return 0;
}