# [NC15553](https://ac.nowcoder.com/acm/problem/15553)
## 题意
给你n个数，选2个长度为k的连续区间，求他们加起来的和最大为多少？
## 思路
前缀和预处理，然后利用前缀和计算k个数的最大数为多少，然后预处理从左边遍历到i为止最大的区间长度为k的和为多少，从右边遍历到i为止最大的区间长度为k的和为多少。
扫一遍要选的第一个区间，扫的过程如果左右还有可以选的区间，则取他们的最大值和选的区间相加，记录最大值即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 2e5 + 5;

ll a[maxn],s[maxn],L[maxn],R[maxn];

int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    int T;cin>>T;
    while(T--){
        ll n,k;
        cin>>n>>k;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            s[i]=s[i-1]+a[i];
            L[i]=-1e18,R[i]=-1e18;
        }
        for(int i=k;i<=n-k;i++){
            L[i]=max(L[i-1],s[i]-s[i-k]);
        }
        for(int i=n-k+1;i>=k+1;i--){
            R[i]=max(R[i+1],s[i+k-1]-s[i-1]);
        }
        ll res=-1e18;
        for(int i=k;i<=n-k;i++){
            res=max(res,L[i]+R[i+1]);
        }
        cout<<res<<&#39;\n&#39;;
    }
    return 0;
}

## 变形
一：不限制长度——在一个数列里找两个不相交区间使得他们权值和最大
二：区间数目变多——找 {m}m个长度为 {k}k 的不相交区间使得他们的权值和最大 $(1\leq n \leq 50001≤n≤5000)$
三：区间数目变多且不限制长度——找 {m}m 个不相交长度不限的区间使得他们权值和最大$(1\leq n \leq 50001≤n≤5000)$
## 思路
一：这题和原题的区别就是区间的长度不固定，显然我们要选出两个不相交的区间，且这两个区间的和加起来要最大（这里要注意不一定是第一大的区间选出来再选一个剩下最大的区间，这样他们的和不一定是最大的）。
$L[i]=((L[i-1]>0)?L[i-1]:0)+a[i]必须选i的情况下左边这段最大的值$
$R[i]=((R[i+1]>0)?R[i+1]:0)+a[i]必须选i的情况下右边这段最大的值$
$mL[i]=max(mL[i-1],L[i])到第i号元素为止左边的最大值$
$mR[i]=max(mR[i+1],R[i])到第i号元素为止右边的最大值$

二：$DP$ 前缀和预处理
整体思想，把k个区间的和看为一个整体，$f[i][j]$表示到i个数为止拿j个区间的和
$f[i][j]=max(f[i-k][j-1]+sum[i]-sum[i-k],f[i-1][j])$

三：分两种情况进行DP（选还是不选第a[i]）。