c++代码




#include <iostream>
#include <cstring>
#include <algorithm>
const int N = 5e4+10;
const int INF=1e9;
using namespace std;

int a[N],f[N],g[N],h[N];

//g[N]存1-i中最大连续子序列和
//h[N]存i-n中最大连续子序列和

int main()
{
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d", &n);
        for(int i=1;i<=n;i++)scanf("%d",a+i);

        f[0]=g[0]=-INF;//防止选到子序列为空的情况
        for(int i=1;i<=n;i++){
            //f[N]存前缀以i为右端点的最大连续子序列和
            f[i]=max(f[i-1],0)+a[i];//比如f[1]=a[1]等于一个负数
            g[i]=max(g[i-1],f[i]);//那么g[1]=max(0,负数)则g[1]=0就错了，实际上g[1]也等于a[1],因为g[0]初始化//为0
        }

        f[n+1]=h[n+1]=-INF;//防止选到子序列为空的情况
        for(int i=n;i;i--){
            //f[N]存后缀以i为左端点的最大连续子序列和
            f[i]=max(0,f[i+1])+a[i];
            h[i]=max(h[i+1],f[i]);
        }

        int res=-INF;
        for(int i=1;i<=n;i++){
            res=max(res,g[i]+h[i+1]);
        }
        printf("%d\n",res);
    }

    return 0;
}