题意

• 给定n个数，求两个长度为k的不连续区间和最大是多少

思路

• 选择两个不重叠区间，必然一个在左，一个在右
• 可以维护一个前缀和，用表示0~i中最大的长度为k的区间的值
• 然后从后往前遍历，取每一个长为k的区间，为右区间，同时通过在O(1)的时间内获得左区间的最大值，两者相加即可
• 也可以直接维护一个前缀和一个后缀和，然后维护两个dp，可读性更好一点

代码

#include<bits/stdc++.h>
using namespace std;

long long dp[302020];
long long a[302020];
int main(){
    int T;
    cin >> T ;
    while(T--){
        
        int n,k;
        cin >> n >> k;
        for(int i=1;i<=n;i++){
            dp[i]=-1e18;
            cin >> a[i];
            a[i]+=a[i-1];
        }

        for(int i=k;i<=n;i++){
            dp[i]=max(dp[i-1],a[i]-a[i-k]);
        }
        long long ans=-1e18;
        for(int i=n-k;i>=k;i--){
            ans=max(ans,dp[i]+(a[i+k]-a[i]));
        }        
        cout << ans << endl;
    }

    return 0;
}