涉及知识点:

前缀和

solution:

题目要求的是两段不连续长度为k的连续区间和
先求一遍前缀和,然后记录第i个位置的前缀和的较大值以及后缀的较大值,最后遍历一遍
答案可能为负数,记得初始化为-inf

std:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 200005;
ll a[maxn],pre[maxn],f[maxn],f1[maxn],f2[maxn];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,k;
        ll ans = -1e18;
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
            pre[i] = pre[i-1] + a[i];
            f1[i] = f2[i] = -1e18;
        }
        for(int i=k;i<=n;i++)
            f[i] = pre[i] - pre[i-k];
        for(int i=k;i<=n;i++)
            f1[i] = max(f1[i-1] , f[i]);
        for(int i=n-k+1;i>=k+1;i--)
            f2[i] = max(f2[i+1] , f[i+k-1]);
        for(int i=k;i<=n-k+1;i++){
            ans = max(ans , f1[i] + f2[i+1]);
        }
        printf("%lld\n",ans);
    }
    return 0;
}