前缀和+后缀最大值（dp）

题目描述：

今天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）。

思路：

先用前缀和进行预处理

再维护一个dp数组，dp[i]表示，i 到 n中长度为k的区间的和的最大值

然后就可以枚举第一个区间，通过O(1)的复杂度得到第二区间的最大值

坑点

要开longlong

数组要开够

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 300000 + 50
#define endl '\n'
#define seed 13331
#define mod 1000000007
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;

inline ll llRead(){ll x(0), t(1);char o (getchar());while (o < '0' || o > '9') {if (o == '-') {t = -1;}o = getchar();}for (; o >= '0' && o <= '9'; o = getchar()) {x = (x << 1) + (x << 3) + (o ^ 48);}return x * t;}



ll t;
ll n, k;
ll tr[MAX];
ll sum[MAX];
ll dp[MAX];

void init(){
    mem(tr, 0);
    mem(dp, 0);
    mem(sum, 0);
}

int main(){
    t = llRead();
    while (t--) {
        init();
        n = llRead();k = llRead();
        for(int i = 1; i <= n; ++i)tr[i] = llRead();
        for(int i = 1; i <= n; ++i)sum[i] = sum[i - 1] + tr[i];
        ll ma = -1e18;
        for(ll i = n; i >= k; --i){
            ma = max(ma, sum[i] - sum[i - k]);
            dp[i] = ma;
        }
        ma = -1e18;
        for(ll i = k; i <= n - k; ++i){
            ma = max(ma, sum[i] - sum[i - k] + dp[i + k]);
        }
        cout<<ma<<endl;
    }
    return 0;
}