AcWing 1051. 最大的和
原题链接
简单
作者:
胡歌-此生不换
,
2022-09-25 13:37:14
,
所有人可见
,
阅读 156
思路:前后缀分解
时间复杂度:O(n)
理解:
- 新开两个数组
int l[N]
和 int r[N]
;
- l 数组记录的是以
l[i]
为最后一个数,向前连续的最大值;
- r 数组记录的是以
r[i]
为第一个数,向后连续的最大值; (要连续哦,因为要的是子数组)
代码实现:
#include <iostream>
#include <cstring>
using namespace std;
const int N = 50010;
int l[N], r[N];
int a[N];
int main(void)
{
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
memset(l, -0x3f, sizeof l);
memset(r, -0x3f, sizeof r);
int temp = 0;
for(int i = 1; i <= n; i++)
{
temp = max(temp, 0) + a[i];
l[i] = max(temp, l[i - 1]);
}
temp = 0;
for(int i = n; i >= 1; i--)
{
temp = max(temp, 0) + a[i];
r[i] = max(temp, r[i + 1]);
}
// int maxv = 0;
int maxv = -0x3f3f3f3f;
for(int i = 1; i <= n; i++)
if(maxv < l[i] + r[i + 1])
maxv = l[i] + r[i + 1]; // l[i] + r[i + 1] 哦,不是 l[i] + r[i]
cout << maxv << endl;
}
return 0;
}