AcWing 1051. 最大的和
原题链接
简单
作者:
zhengyh
,
2021-02-04 16:51:48
,
所有人可见
,
阅读 384
#include <bits/stdc++.h>
using namespace std;
const int N = 50010;
int a[N], pre[N], suf[N], premx[N], sufmx[N];
int main()
{
int T; cin >> T;
while(T -- )
{
int n, res = -0x3f3f3f3f; cin >> n;
for(int i = 1 ; i <= n ; i ++ ) cin >> a[i];
for(int i = 0 ; i <= n+1 ; i ++ ) pre[i] = suf[i] = sufmx[i] = premx[i] = -0x3f3f3f3f;
for(int i = 1 ; i <= n ; i ++ )
{
pre[i] = max(0, pre[i-1]) + a[i];
}
for(int i = n ; i >= 1 ; i -- )
{
suf[i] = max(0, suf[i+1]) + a[i];
}
for(int i = 1 ; i <= n ; i ++ )
{
premx[i] = max(premx[i-1], pre[i]);
}
for(int i = n ; i >= 1 ; i -- )
{
sufmx[i] = max(sufmx[i+1], suf[i]);
}
for(int i = 1 ; i < n ; i ++ )
{
res = max(res, premx[i] + sufmx[i+1]);
}
cout << res << endl;
}
return 0;
}