牛客课后1.4 数学考试 题解

题目大意

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

解题思路

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

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

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

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

（wa了一发，气死了。。

完整代码

#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;
	}
}