题解 | #数学考试#

思路

用前缀和去处理[L,L+1,L+2,....,L+k-1]，[R,R+1,R+2,...,R+k-1]的和。
重点是这两个区间不相交，我们如果去枚举两个区间的位置肯定会超时的。
那么我们可以考虑一个指针从k出发到n-k，移动过程中记录左边区间的最大值，（可能不变）
同时我们右边区间是不断变化的，两者相加的最大值就是答案。

代码

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;

ll t,n,k,a[200005],sm[200005],ans=0,lf;

int main(){
    scanf("%lld",&t);
    while(t--){
        lf=-1e15,ans=-1e15;
        scanf("%lld%lld",&n,&k);
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
            sm[i]=sm[i-1]+a[i];
        }
        for(int i=k;i<=n-k;i++){
                lf=max(lf,sm[i]-sm[i-k]);
                ans=max(ans,sm[i+k]-sm[i]+lf);
        }
        printf("%lld\n",ans);
    }
    return 0; 
}