Solution

由题意可知需要求两段不连续区间，使和最大。

区间求和问题可以想到一个常用算法：前缀和。区间 的和可以用 方便地求出。

预处理序列的前缀和后，如何得知某个位置之前和之后的和最大的区间呢？我们可以使用线性 求得。设 表示位置 之前的最大区间和， 表示位置 之后的最大区间和。那么有：

• {，}
• {，}

由于数据范围较大，需要开。注意 数组初始化为负无穷。

时间复杂度：。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
const int maxn=2e5+10;
ll t,n,k,ans,a[maxn],sum[maxn],f1[maxn],f2[maxn];
int main(){
    cin>>t;
    while(t--){
        memset(f1,-0x7f,sizeof(f1));
        memset(f2,-0x7f,sizeof(f2));
        cin>>n>>k;
        ans=-1e18;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            sum[i]=a[i]+sum[i-1];
        }
        for(int i=k;i<=n-k;i++)
            f1[i]=max(sum[i]-sum[i-k],f1[i-1]);
        for(int i=n-k+1;i>=k+1;i--)
            f2[i]=max(sum[i+k-1]-sum[i-1],f2[i+1]);
        for(int i=k;i<=n-k;i++)
            ans=max(ans,f1[i]+f2[i+1]);
        cout<<ans<<endl;
    }
    return 0;
}

也可以来我的博客看 https://www.luogu.com.cn/blog/taiqi/post-niu-ke-mei-ri-yi-ti