数学考试——DP

链接：https://ac.nowcoder.com/acm/problem/15553
来源：牛客网

题目描述
今天qwb要参加一个数学考试，这套试卷一共有n道题，每道题qwb能获得的分数为ai，qwb并不打算把这些题全做完，
他想选总共2k道题来做，并且期望他能获得的分数尽可能的大，他准备选2个不连续的长度为k的区间,
即[L,L+1,L+2,....,L+k-1]，[R,R+1,R+2,...,R+k-1]（R >= L+k）。
输入描述:
第一行一个整数T（T<=10）,代表有T组数据
接下来一行两个整数n,k,(1<=n<=200,000),(1<=k,2k <= n)
接下来一行n个整数a1,a2,...,an，（-100,000<=ai<=100,000）
输出描述:
输出一个整数，qwb能获得的最大分数
示例1
输入
2
6 3
1 1 1 1 1 1
8 2
-1 0 2 -1 -1 2 3 -1
输出
6
7
对于区间和的问题，首先肯定要用前缀和处理。选两个k长度的区间使得和最大，暴力为O（n^2）,是不行的。我们注意到在暴力的过程中，已经选好一个区间，要再选另一个区间，我们的方法是一个一个枚举，但是我们需要的仅仅是最大的那个区间。或许我们会想到只枚举第一个区间，然后经过处理，使得能求出另一个区间的最大值，但这也不容易。
我们发现我们能用递归方便得求出一个连续区间的最大子序列，但是中间扣去一个区间后，每种情况便无法递归了。所以我们可以把选取区间左边和右边的最大子序列求出存到两个数组中，下标代表第一个枚举的的数组，再取最大值。
但是我们又想到，其实这个过程还是有重复的，因为第一次枚举区间和第二次最大值的区间也是互相对应的。我们再想想，能不能优化。
之所以会重复实际上是因为这两个数是等价的，那我们就需要把他们赋予不同的含义，因此我们可以将第一个枚举的区间定为是相对右的，所以我们只需要在枚举区间的左边所有区间中选取最大区间就行了。
最后在实际写代码的时候，我们还可以把枚举和选最大区间合并起来，只用一个循环。

#include <iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>

typedef long long ll;

using namespace std;

int main()
{
    ll ans;
    int T, n, k;
    ll lmax = 0;
    cin >> T;
    while (T--)
    {
        lmax = -1e18, ans = -1e18;
        cin >> n >> k;
        vector<ll> v(n + 1);
        v[0] = 0;
        for (int i = 1; i <= n; i++)
        {
            cin >> v[i];
            v[i] += v[i - 1];
        }
        for (int i = k; i + k <= n; i++)
        {
            lmax = max(lmax, v[i] - v[i - k]);
            ans = max(ans, lmax+v[i + k] - v[i]);
        }
        cout << ans << endl;
    }
}