数学考试

题意:在长度为n的区间上选取长度为k的两个区间,且两个区间不相交,然后输出两个区间求和,并且最大
题解:先求一个前缀和sum,
然后正着dp1数组,就是dp1[i]=max(dp1[i-1],sum[i]-sum[i-k])
再按照dp1的原理反着求dp2数组
然后再过一遍求最大值

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+1;
const ll inf=1e18+1;
ll t,dp1[maxn],dp2[maxn],sum[maxn],ans=-inf;
int main()
{
    int n,k,T;
    scanf("%d",&T);
    while(T--)
    {
        ll ans=-inf;
        scanf("%d %d",&n,&k);
        for(int i=1;i<=n;++i) scanf("%lld",&t),sum[i]=sum[i-1]+t,dp1[i]=dp2[i]=-inf;
        for(int i=k;i<=n-k;++i) dp1[i]=max(dp1[i-1],sum[i]-sum[i-k]);
        for(int i=n-k+1;i>k;--i) dp2[i]=max(dp2[i-1],sum[i+k-1]-sum[i-1]);
        for(int i=k;i<=n-k;++i) ans=max(ans,dp1[i]+dp2[i+1]);
        printf("%lld\n",ans);
    }
}