数学考试(前缀和)

链接：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能获得的最大分数
链接：https://ac.nowcoder.com/acm/problem/15553
来源：牛客网

示例1
输入
2
6 3
1 1 1 1 1 1
8 2
-1 0 2 -1 -1 2 3 -1
输出
6
7

题意：略
题记：前缀和记录方便区间查找。先选取第一个区间的最大值，做法是枚举区间右端点，并用mmax更新第一个区间的最大值；然后再选取第二个区间的最大值，做法是枚举区间左端点，并记录下区间的最大值。我们发现枚举第二个区间的时候可以和第一个区间的枚举过程合并。复杂度O（n）

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7;
typedef long long ll;
ll a[N];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--) {
        int n, k;
        scanf("%d%d",&n,&k);
        for(int i=1; i<=n; i++) {
            scanf("%lld",&a[i]);
            a[i]=a[i-1]+a[i];
        }

        ll ans=-1e18,mmax=-1e18; 
        for(int i=k; i+k<=n; i++) {
            mmax=max(mmax,a[i]-a[i-k]);
            ans=max(ans,mmax+a[i+k]-a[i]);
        }
        printf("%lld\n",ans);
    }
}