牛客课后1.4 数学考试 题解

题目大意

给你n个数,求两个不重合且长度为k的两个区间的最大和。

解题思路

首先肯定需要用前缀和,然后直接暴力一发,T了。

后面想可以用一个前缀数组来表示前i的最大和,一个后缀数组表示i后最大和,结果wa了。

看了题解,发现只需要定一个就行了,另外一个表示这个区间之前满足要求的最大区间和。

注意答案初始化为-1e18。

(wa了一发,气死了。。

完整代码

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
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
const int N = 2e5 + 5;
ll num[N], sum[N], ans[N];

int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t; cin >> t;
while (t--) {
int n, k; cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> num[i];
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + num[i];
}
ll ans = -1e9, pre = -1e9;
for (int l = k + 1;l + k - 1 <= n; l++) {
pre = max(pre, sum[l - 1] - sum[l - k - 1]);
ans = max(ans, pre + sum[l + k - 1] - sum[l - 1]);
}
cout << ans << endl;
}
}
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!
  • © 2015-2021 sakurakarma
  • Powered by Hexo Theme Ayer
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信