思路:前后缀分解
相似的题:
构建乘积数组
股票买卖 III
#include<iostream>
#include<vector>
using namespace std;
using namespace std;
// 前后缀分解
// 两个相关问题,分成两半,枚举分割点
// 预处理两半
// 然后再枚举 分割点即可
class Solve {
private:
static constexpr int INF = 0x3f3f3f3f;
public:
Solve(int _n) : n(_n), nums(n + 1), f(n + 1, -INF), g(n + 1,-INF)
{
for (int i = 1; i <= n; ++i) cin >> nums[i];
}
void operator()()
{
int prev = 0;
// 预处理左边
for(int i = 1;i <= n; ++ i)
{
prev = max(prev, 0) + nums[i];
f[i] = max(f[i - 1], prev);
}
prev = 0;
// 预处理右边
for(int i = n;i >= 1; -- i)
{
prev = max(prev, 0) + nums[i];
g[i] = max(g[i + 1], prev);
}
// 枚举分割点 [1, n) 保证分割
int res = -INF;
for(int i = 1;i < n; ++ i)
res = max(res, f[i] + g[i + 1]);
cout << res << endl;
}
private:
int n;
vector<int> nums;
// f[i]表示 [0, i]最大连续序列值
// g[i]表示 [i + 1, n] 中的最大连续序列的值
vector<int> f, g;
};
int main()
{
ios::sync_with_stdio(false);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
Solve{n}();
}
return 0;
}
犇犇犇,Orz Orz