soltion

我们可以预处理出一个L数组，其中表示以i为右端点的长度为k的区间和。然后预处理一个数组表示以i为左端点的长度为k的区间和。这两个数组都可以通过预处理前缀和然后相减的方法得到。即：记为区间的数字和，那么区间的数字和就是

然后考虑如何找到两个最大的不相交的长度为k的区间，很容易想到对做一个前缀最大值，对做一个后缀最大值。然后枚举一下左边区间的右端点，找到右边区间中的最大值就可以保证两个区间不相交了。

单组数据复杂度

注意因为输入有负数，所以赋的初值应为极小值而不是0.

code

/*
* @Author: wxyww
* @Date: 2020-04-02 14:08:41
* @Last Modified time: 2020-04-02 14:16:44
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 200010;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
ll a[N],L[N],R[N];
int main() {
    int T = read();
    while(T--) {
        int n = read(),k = read();
        memset(L,-0x3f,sizeof(L));
        memset(R,-0x3f,sizeof(R));
        for(int i = 1;i <= n;++i)
            a[i] = a[i - 1] + read();
        for(int i = k;i <= n;++i)
            L[i] = max(L[i - 1],a[i] - a[i - k]);
        for(int i = n - k + 1;i >= 1;--i)
            R[i] = max(R[i + 1],a[i + k - 1] - a[i - 1]);
        ll ans = -1e15;
        for(int i = k;i + k <= n;++i)
            ans = max(ans,L[i] + R[i + 1]);
        cout<<ans<<endl;
    }
    return 0;
}