【题解】一本通1305 Maximum sum

信息学奥赛一本通：经典算法Baidu搜索，深刻体会。

题意

给出一个数列 求它最大的两个不重合子段的和

分析

本题是"最大子段和"的升级版 需要求两个字段 而且卡时间只能使用 $O(nt)$ 做法

可使用普通 $O(n)$ dp 分别正反方向各扫一遍 得到 $dp1$ 与 $dp2$ 数组

$dp1_i$ : 前 $i$ 个数最大子段和

$dp2_i$ : 后 $i$ 个数最大子段和

直接求出最大的 $dp1_i + dp2_j (i<j)$ 即为答案！

然后等你写完代码交上去…TLE

为什么会TLE? 因为"求出最大的 $dp1_i + dp2_j (i<j)$ "的朴素做法是 $O(n^2)$ 的

可以空间换时间，开个 $pre$ 数组和 $suf$ 数组分别表示前 $i$ 个 $dp1_i$ 和后 $i$ 个 $dp2_i$ 的最大值

于是 $O(n)$ 扫一遍求 $pre_{i-1} + suf_{i}$ 的最大值就 $\color{green}{AC}$ 了！

别忘了加读入优化 阴间一本通卡cin

#include <iostream>
#include <numeric>
#include <cstring>
using namespace std;
int t, n, res, arr[50010], sum[50010], dp1[50010], dp2[50010], pre[50010], suf[50010];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> t;
	while(t--) {
		cin >> n;
		for(int i = 1; i <= n; i++)	cin >> arr[i];
		memset(sum, 128, sizeof(sum));
		memset(dp1, 128, sizeof(dp1));
		memset(dp2, 128, sizeof(dp2));
		memset(pre, 128, sizeof(pre));
		memset(suf, 128, sizeof(suf));
		res = -0x3f3f3f3f;
		partial_sum(arr + 1, arr + 1 + n, sum);
		for(int i = 1; i <= n; i++)	dp1[i] = max(dp1[i - 1] + arr[i], arr[i]);
		for(int i = n; i >= 1; i--)	dp2[i] = max(dp2[i + 1] + arr[i], arr[i]);
		for(int i = 1; i <= n; i++)	pre[i] = max(pre[i - 1], dp1[i]);
		for(int i = n; i >= 1; i--)	suf[i] = max(suf[i + 1], dp2[i]);
		for(int i = 2; i <= n; i++)	res = max(res, pre[i - 1] + suf[i]);
		cout << res << endl;
	}
	system("pause");
	return 0;
}