题目链接:
AcWing 牛客
题目描述
输入一个长度为n的整数序列,从中找出一段不超过m的连续子序列,使得整个序列的和最大。 例如 1,-3,5,1,-2,3 当m=4时,S=5+1-2+3=7 当m=2或m=3时,S=5+1=6
输入描述:
第一行两个数n,m($n,m \leq 300000$) 第二行有n个数,要求在n个数找到最大子序和
输出描述:
一个数,数出他们的最大子序和
示例1
输入
6 4
1 -3 5 1 -2 3
输出
7
思路 单调队列
单调队列模板题
首先这是区间和的问题,先求前缀和 $sum$。题目转化为求最大的 $sum[r] - sum[l]$ 且 $r - l <= m$。
枚举右端点 $r$,维护左端点 $l \in [r - m, r - 1]$,保持 $sum[l]$ 最小。
如果某个位置 $k < l$,且 $sum[k] \ge sum[l]$,那么直接舍弃 $k$。因为 $l$ 更靠近 $r$ 且 $sum[l] <= sum[k]$,这意味着 $l$ 的生存能力更强。
因此维护一个前缀和递增的单调队列,保持队尾的元素的下标与队首的元素的下标之差不超过 $m$。
代码 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 30 31 32 33 34 #include <bits/stdc++.h> using namespace std ;typedef long long ll;const int maxn = 3e5 + 10 ;int n, m;ll sum[maxn]; int q[maxn];void solve () { ll ans = 0 ; int l = 1 , r = 1 ; q[l] = 0 ; for (int i = 1 ; i <= n; ++i) { while (l <= r && i - q[l] > m) ++l; ans = max(ans, sum[i] - sum[q[l]]); while (l <= r && sum[i] <= sum[q[r]]) --r; q[++r] = i; } cout << ans << endl ; } int main () { ios::sync_with_stdio(false ); cin .tie(0 ); cin >> n >> m; for (int i = 1 ; i <= n; ++i) { ll x; cin >> x; sum[i] = sum[i - 1 ] + x; } solve(); return 0 ; }
deque 版本
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 30 31 32 33 34 35 #include <bits/stdc++.h> using namespace std ;typedef long long ll;const int maxn = 3e5 + 10 ;int n, m;struct Node { int id; ll val; } node[maxn]; void solve () { ll ans = 0 ; deque <Node> q; for (int i = 1 ; i <= n; ++i) { while (!q.empty() && i - q.front().id > m) q.pop_front(); ans = max(ans, node[i].val - q.front().val); while (!q.empty() && node[i].val <= q.back().val) q.pop_back(); q.push_back(node[i]); } cout << ans << endl ; } int main () { ios::sync_with_stdio(false ); cin .tie(0 ); cin >> n >> m; for (int i = 1 ; i <= n; ++i) { ll x; cin >> x; node[i].val = node[i - 1 ].val + x; node[i].id = i; } solve(); return 0 ; }
参考
《算法竞赛进阶指南》 李煜东 著