AcWing 1051. 最大的和-前后缀分解
原题链接
简单
作者:
AndSonder
,
2022-02-22 17:11:42
,
所有人可见
,
阅读 161
代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 50010;
int nums[N];
int f[N]; // 存储以nums[i]结尾的序列中最大的和
int g[N]; // 存储以nums[i]开头的序列中最大的和
int main()
{
int n;
cin >> n;
while(n--)
{
memset(nums,-0x3f,sizeof nums);
memset(f,-0x3f,sizeof f);
memset(g,-0x3f,sizeof g);
int t;
cin >> t;
for(int i = 1;i <= t;i++) cin >> nums[i];
int s = 0; // 存储以0 - nums[i-1]中的最大序列和
for(int i = 1;i <= t;i++)
{
s = max(0, s) + nums[i];
f[i] = max(f[i-1], s);
}
s = 0; // 存储以nums[i+1]- t中的最大序列和
for(int i = t;i >= 1;i--)
{
s = max(0, s) + nums[i];
g[i] = max(s,g[i+1]);
}
int res = -0x3f3f3f3f;
for(int i = 1;i < t;i++)
res = max(res,f[i] + g[i+1]);
cout << res << endl;
}
}