题目描述
写的不好看,但是思路还是挺清晰的,
1 分别从左到右,从右到左,求最大的和的子序列,
2 分别求左、右两边可以取到的最大子序列的值,。
3 扫一遍 左边+右边=全部
坑点
1 边界情况要处理好,搞得我调试了好久,
2 多组输入,上一次输入的值可能还在数组里面,不是0,对结果造成影响导致WA
代码
#include <iostream>
using namespace std;
const int N= 5e4+10;
int a[N], b[N];
int main () {
int t , n;
cin >> t;
while (t--) {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
b[i] = a[i];
if (i > 1) a[i] = max(a[i-1], 0) + a[i];
}
for (int i = 2; i <= n; i++) {
a[i] = max(a[i], a[i - 1]);
}
for (int i = n - 1; i >= 1; i--) {
b[i] = max(b[i+1], 0) + b[i];
}
for (int i = n - 1; i >= 1; i--) {
b[i] = max(b[i+1], b[i]);
}
int ans = -1e9;
for (int i = 1; i <= n - 1; i++) {
ans = max(ans, a[i] + b[i + 1]);
//cout << a[i] << ' ';
}
cout << ans << endl;
}
return 0;
}