NC15553 数学考试

链接：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

选择的左边这个区间是 [l,r] 的话，右边的区间一定是 r 右边的所以长度为 k 的区间里面和最大的那个，这个只需要从右往左扫描一遍就可以维护出来——如果我们用 ans[i] 表示 i 右边的所有长度为 k 的区间的和的最大值，那么 ans[i]=max(ans[i+1],num[i+k−1]−num[i−1])（要么是i+1右边长度为 k 的区间的最大值，要么是从 i 开始向右长度为 k 的区间）。
这样就在 i 的位置形成分割线，i 后的为ans[i], i 前的为 num[i-1]-num[i-k-1]，那么直接用res取最大的和
res=max(res,ans[i]+num[i-1]-num[i-k-1])
注意点是：赋初值时要为 -1e18 ，题目的数据可以为负数。

#include <bits/stdc++.h>
#define MAX_INT  ((unsigned)(-1)>>1)
#define MIN_INT  (~MAX_INT)
#define db printf("where!\n");
using namespace std;
#define ll long long
template<class T>inline void read(T &res){
char c;T flag=1;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
ll a;
ll num[200005];
ll ans[200005];
int main()
{
    int t;cin>>t;
    while(t--){
        memset(ans,-0x7f,sizeof ans);
        ll res=-1e18;
        int n,k;cin>>n>>k;
        for(int i=1;i<=n;i++){
            read(a);
            num[i]=num[i-1]+a;
        }
        for(int i=n-k+1;i>k;i--){
            ans[i]=max(ans[i+1],num[i+k-1]-num[i-1]);
            res=max(res,ans[i]+num[i-1]-num[i-k-1]);
        }
        cout<<res<<endl;
    }
    return 0;
}