数学考试
遇到过很多次的套路了,分成前面的贡献和后面的贡献,然后枚举位置直接拼起来即可。
具体来说\(fi\)表示区间右端点小于等于i的所有区间长度为k的最大值,
gi类似
#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
using namespace std;
typedef long long ll;
const int N=2e5+5;
const ll inf=1ll<<60;
int a,n,k;
ll s[N],f[N],g[N],ans;
int main(){
// freopen("data.in","r",stdin);
// freopen("data.out","w",stdout);
int T;
scanf("%d",&T);
while (T--){
scanf("%d %d",&n,&k);
fo(i,1,n) {
scanf("%d",&a);
s[i]=s[i-1]+a;
}
fo(i,1,n+1) f[i]=g[i]=-inf;
ans=-inf;
fo(i,k,n) {
f[i]=max(f[i-1],s[i]-s[i-k]);
}
fd(i,n-k+1,1) {
g[i]=max(g[i+1],s[i+k-1]-s[i-1]);
}
fo(i,1,n) ans=max(ans,f[i]+g[i+1]);
printf("%lld\n",ans);
}
return 0;
}