【每日一题】3月27日每日一题题解（求两段不相交的长度为k的区间数之和的最大值）

Update：线段树题解已更新：https://blog.nowcoder.net/n/7c67622afee94322af471bf99ff6ed6b

计 为 区间内，所有的 这样的区间中，数之和的最大值。
那么只要遍历一遍，当左区间取 时，右区间的最大值可以 读取，即 。
所有以上计算均可以用前缀和达成 预处理。
完整代码如下：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll sum[422222],a[422222];
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,k,i;
        cin>>n>>k;
        for(i=1;i<=n;i++)scanf("%lld",&a[i]);
        ll s=0;
        for(i=1;i<=n;i++){      //前缀和
           s+=a[i];
           sum[i]=s;
        }
        ll dp[222222]={0};   //dp[i]代表[i-k,i]到[n-k,n]这些所有的区间，和的最大值。
        ll ma=-1e18;
        for(i=n;i>=k;i--){
            ma=max(ma,sum[i]-sum[i-k]);
            dp[i]=ma;
        }
        ma=-1e18;
        for(i=k;i<=n-k;i++){
            ma=max(ma,sum[i]-sum[i-k]+dp[i+k]);
        }
        cout<<ma<<endl;
    }
}