数学考试

设为之间所有的最大值

那么我们只要遍历一遍当左区间取到的时候，另一个区间的最大值就是

利用前缀和从右往左维护 maxn为从右往左维护时记录的最大值

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 200000 + 7;
ll sum[MAXN] , a[MAXN];

int main(void){
    int T;
    cin>>T;
    while(T--){
        int n , k;
        cin>>n>>k;
        for(int i = 1 ; i <= n ; ++i){
            scanf("%lld" , &a[i]);
        }
        ll s = 0;
        for(int i = 1 ; i <= n ; ++i){
            s += a[i];
            sum[i] = s;
        }
        ll dp[MAXN] = {0};
        ll d = -1e18;
        for(int i = n ; i >= k ; --i){
            d = max(d , sum[i] - sum[i - k]);
            dp[i] = d;
        }
        d = -1e18;
        for(int i = k ; i <= n - k ; ++i){
            d = max(d , sum[i] - sum[i - k] + dp[i + k]);
        }
        cout<<d<<endl;
    }
    return 0;
}