考虑到题目给的内存有点小，开一颗线段树重复利用，每次得到的值用另一数组记录一下即可，这样就能转化成区间最大问题了。不懂看代码！！！

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
inline int Read(){
    int e = 0; char ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    while('0' <= ch && ch <= '9') e = e*10 + (ch-'0'), ch = getchar();
    return e;
}

const int maxn = 1e5 + 7;
int tree[maxn<<2], k[maxn], s[maxn];

inline int max(int u, int v){
    return u>v? u: v;
}

void Buildtree(int l, int r, int key){
    if(l == r){
        tree[key] = k[l];
        return;
    }
    int mid = (l + r) >> 1;
    Buildtree(l, mid, key<<1);
    Buildtree(mid+1, r, key<<1|1);
    tree[key] = max(tree[key<<1], tree[key<<1|1]);
}

int Query(int l, int r, int ls, int rs, int key){
    if(ls <= l && r <= rs) return tree[key];
    int mid = (l + r) >> 1, ans = 0;
    if(ls <= mid) ans = max(ans, Query(l, mid, ls, rs, key<<1));
    if(mid < rs) ans = max(ans, Query(mid+1, r, ls, rs, key<<1|1));
    return ans;
}

int main(){
    int t = Read(), n, len;
    while(t --){
        n = Read();
        for(int i = 1; i <= n; i ++) k[i] = Read();
        len = Read();
        for(int i = 1; i <= n; i ++){
            k[i] += k[i-1];
            s[i] = k[i] - k[max(i-len, 0)];
        }
        for(int i = 1; i <= n; i ++) k[i] = s[i];
        Buildtree(1, n, 1);
        for(int i = len+1; i <= n; i ++) k[i] = Query(1, n, 1, i-len, 1) + s[i];
        Buildtree(1, n, 1);
        int ans = 0;
        for(int i = 2*len+1; i <= n; i ++){
            k[i] = Query(1, n, 1, i-len, 1) + s[i];
            ans = max(k[i], ans);
        }
        printf("%d\n", ans);
    }
    return 0;
}