题目：https://ac.nowcoder.com/discuss/392146?type=101&order=0&pos=5&page=1

题解：

题型1：限制区间长度k，区间段数2，做法o(n)

用前缀和思想表示区间，区间和SUM[l...r]=sum[r]-sum[l-1]。
末尾位置i的长度为k的区间和为sum[i]-sum[i-k]。
考虑枚举第二段区间【i-k,i】的位置，然后只要从【1,i-k-1】中取最大的区间，遍历的时候用一个变量维护一下【1,i-k-1】的最大值就好了。
代码：

#include
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll sum[200005];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,k;
        scanf("%d%d",&n,&k);
        ll maxx=-1e18;
        for(int i=1;i<=k;i++)
        {
            int x;
            scanf("%d",&x);
            sum[i]=sum[i-1]+x;
        }
        ll ans=-1e18;
        for(int i=k+1;i<=n;i++)
        {
            int x;
            scanf("%d",&x);
            sum[i]=sum[i-1]+x;
            if(i>=2*k)
            {
                maxx=max(maxx,sum[i-k]-sum[i-k-k]);
                ans=max(ans,sum[i]-sum[i-k]+maxx);
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}

题型2：不限制区间长度，区间段数2，做法o(n)

同样用前缀和思想表示区间。
问题就变成了找四个位置l1,r1,l2,r2，使得sum[r1]-sum[l1-1]+sum[r2]-sum[l2-1]最大，其中r2>l2-1>=r1>l1-1。
可以先预处理出【1,i】内一段区间的最大值。
然后枚举第二段区间的起始位置l1，这样第一段区间肯定取【1,i】里一段区间的最大值，第二段区间的结束位置肯定取【l2,n】的最大值，再从每次枚举的结果中取最大值即可。
代码：

#&*%*&#(口糊)

题型3：限制长度k，区间段数m，做法o(n*m)

显然，m段的情况可以从m-1段的情况转移过来。
考虑动态规划dp[i][j]表示区间【1,i】中取j段区间的最大值。
转移是考虑当前位置i是否作为区间的结束位置。
于是得到转移方程dp[i][j]=max(dp[i-1][j],dp[i-k][j-1]+sum[i]-sum[i-k]);
这样就好了。

题型4：不限制区间长度，区间段数m，做法o(n*m)

（已修）
同样考虑动态规划dp[i][j]表示区间【1,i】中取j段区间的最大值。
转移同样考虑当前位置i是否取做区间右端。
用MIN【l,r】表示区间l到r中的最小前缀。
于是得到转移方程dp[i][j]=max(dp[i-1][j],dp[t][j-1]+sum[i]-MIN【t,i-1】),(其中1<=t<=i-1)
然后发现这样暴力转移是o(n²m)。
考虑dp[i][j]的转移和dp[i+1][j]的转移的差异。
多了前缀和sum[i]和dp[i][j-1]两个东西
所以我们只要在前面的基础上，多考虑是否取sum[i]作为新区间左端，和是否取dp[i][j-1]做原转移位置。
得到新的转移方程。
MM[i+1]=max(MM[i],dp[i][j-1]);
A[i+1][j]=max(A[i][j],MM[i]-sum[i])-sum[i]+sum[i+1];
dp[i+1][j]=max(dp[i][j],A[i+1][j])
好像就可以了。