题目描述
最大子序和
求长度不超过 m 的连续子序列 的最大值
样例
6 4
1 -3 5 1 -2 3
输出
7
单调队列??
no
直接暴力
第一眼以为是 dp 结果有限制条件 m
.......
他不过就是要以每个点为结尾的长度不超过m的最大值
那么每个点直接暴力搜索与他之前的长度不超过m的最大值
然后枚举所有点的情况 取最大值就好了
发现线段树可以快速解决这个问题(分块也行)
解法
令 i 从 1 到 n 遍历一遍数组
对于每个点 他所能维护的子段和 不过是 [max(1, i - m + 1), i]
对于每个点 他的最大子段和 也一样是 [max(1, i - m + 1), i]
所以用线段树或者分块支持区间修改 区间查询 维护最大值 即可
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 5;
ll tree[maxn << 4], lazy[maxn << 4];
void add(int l, int r, int cnt, int L, int R, ll val) {
if (l >= L && r <= R) {
tree[cnt] += val;
lazy[cnt] += val; return;
} int mid = (l + r) >> 1;
if (mid >= L) add(l, mid, cnt << 1, L, R, val);
if (mid < R) add(mid + 1, r, cnt << 1|1, L, R, val);
tree[cnt] = max(tree[cnt << 1], tree[cnt << 1|1]) + lazy[cnt];
}
ll query(int l, int r, int cnt, int L, int R, ll val) {
if (l >= L && r <= R) {
return tree[cnt] + val;
} int mid = (l + r) >> 1;
ll ans = -(1ll << 60);
if (mid >= L) ans = max(ans, query(l, mid, cnt << 1, L, R, val + lazy[cnt]));
if (mid < R) ans = max(ans, query(mid + 1, r, cnt << 1|1, L, R, val + lazy[cnt]));
return ans;
}
int main() {
int n, m; cin >> n >> m;
ll max_ = -(1ll << 60);
for (int i = 1, val; i <= n; ++i) {
scanf("%d", &val); add(1, n, 1, max(1, (i - m + 1)), i, val);
max_ = max(max_, query(1, n, 1, 1, i, 0));
} cout << max_ << endl;
return 0;
}
顺带试了试分块
过不了呜呜....
3e5 * sqrt(3e5) = 1e8 刚好过不了///
要是多给两秒就好了