题意
找到两个不连续且长度为k的序列,使这两个序列和最大。
思路
用前缀和记录下前i个元素的和,然后从前往后遍历,依次记录当前序列和最大的值(ma),以及更新两个序列和的最大值(ans)。
可以很容易想到ma = max(ma, a[i] - a[i - k]), ans = max(ans, ma + a[i + k] - a[i])
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int t;
cin >> t;
while (t--) {
int n,k;
cin >> n >> k;
long long a[200100];
a[0] = 0;
for (int i=1;i<=n;i++) {
cin >> a[i];
a[i] += a[i-1];
}
long long ans=-1000000000000,ma=-1000000000000;
for (int i=k;i<=n-k;i++) {
ma = max(ma,a[i]-a[i-k]);
ans = max(ans,ma+a[i+k]-a[i]);
}
cout << ans << endl;
}
return 0;
}