一本通1305 Maximum sum

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

题意

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

分析

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

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

dp1idp1_i : 前 ii 个数最大子段和

dp2idp2_i : 后 ii 个数最大子段和

直接求出最大的 dp1i+dp2j(i<j)dp1_i + dp2_j (i<j) 即为答案!

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

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

可以空间换时间,开个 prepre 数组和 sufsuf 数组分别表示前 iidp1idp1_i 和后 iidp2idp2_i 的最大值

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#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;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!