AcWing 1051. 最大的和
原题链接
简单
作者:
史一帆
,
2021-05-16 15:29:36
,
所有人可见
,
阅读 222
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 50010;
int n;
int a[N], h[N], t[N]; // a[]存数组的元素
//h[]存从前往后算每个点以前的最大连续子序列
//t[]存从后往前算每个点以后的最大连续子序列
int main()
{
int T;
cin >> T;
while (T -- )
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
h[0] = -1e5;
for (int i = 1, j = 0; i <= n; i ++ ) //从前往后算每个点以前的最大连续子序列
{
j = max(j, 0) + a[i]; //贪心算法,只要前缀和小于0就丢弃
h[i] = max(j, h[i - 1]);
}
t[n + 1] = -1e5;
for (int i = n, j = 0; i >= 0; i -- ) //从后往前算每个点以后的最大连续子序列
{
j = max(j, 0) + a[i];
t[i] = max(j, t[i + 1]);
}
int res = -1e5;
for (int i = 1; i <= n; i ++ ) //以当前点为分割点的最大连续子序列
res = max(res, h[i] + t[i + 1]); // = 左边的最大连续子序列+右边的最大连续子序列
cout << res << endl;
}
return 0;
}