数学考试

Problem:

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

Solution:

需要两个不相交并且两区间和的和最大的区间(此处区间长度固定为k),假如第一个区间是[l,r],那么另一个区间只能是[1,l)或(r,n]
而若我们枚举第一个区间的起点s,得出来的区间就是[s,s + k - 1],那么另一个区间我们只需要考虑在[s + k,n]就好了,最终我们不断计算枚举出
的两个区间的和就好了,最终最大的就是答案。
区间[s + k,n]的最大和 我们可以通过预处理一个数组ssm，ssm[i]表示[i,n]区间长度为k的最大和是多少，那么 [s + k,n]的最大和 == ssm[s + k]
最终我们就可以计算出我们想要的答案了。
区间和可以计算出前缀和！！
注意初始化要为负无穷，不能为0

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define _for(i,s,t) for(int i=s;i<t;i++)
#define _rof(i,s,t) for(int i=s;i>t;i--)
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define per(i,s,t) for(int i=s;i>=t;i--)
#define Ri(x) scanf("%d",&x)
#define Rii(x,y) scanf("%d%d",&x,&y)
#define INF 0x3f3f3f3f
using namespace std;
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;
}
typedef long long ll;
const int maxn = 2e5 + 10;
ll a[maxn],sum[maxn],ssm[maxn];
int main(){
    IOS;
    int T,n,k;
    cin>>T;
    while(T--){
        cin>>n>>k;
        rep(i,1,n){
            cin>>a[i];
            sum[i] = sum[i - 1] + a[i];
            ssm[i] = -1e18;
        }
        per(i,n - k + 1,1){
            ssm[i] = max(ssm[i + 1],sum[i + k - 1] - sum[i - 1]);
        }
        ll ans = -1e18;
        rep(i,1,n - k * 2 + 1){
            ans = max(ans,sum[i + k - 1] - sum[i - 1] + ssm[i + k]);
        }
        cout<<ans<<endl;
    }
    return 0;
}
/**
Problem:
今天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）。
Solution:
    需要两个不相交并且两区间和的和最大的区间(此处区间长度固定为k),假如第一个区间是[l,r],那么另一个区间只能是[1,l)或(r,n]
    而若我们枚举第一个区间的起点s,得出来的区间就是[s,s + k - 1],那么另一个区间我们只需要考虑在[s + k,n]就好了,最终我们不断计算枚举出
    的两个区间的和就好了,最终最大的就是答案。
    区间[s + k,n]的最大和 我们可以通过预处理一个数组ssm，ssm[i]表示[i,n]区间长度为k的最大和是多少，那么 [s + k,n]的最大和 == ssm[s + k] 
    最终我们就可以计算出我们想要的答案了。
    区间和可以计算出前缀和！！     
*/