AcWing 1051. 最大的和
原题链接
简单
作者:
Kingah
,
2023-05-26 23:20:26
,
所有人可见
,
阅读 49
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;
}