【每日一题】数学考试

原题链接：

https://ac.nowcoder.com/acm/problem/15553

题目大意：

今天qwb要参加一个数学考试，这套试卷一共有道题，每道题qwb能获得的分数为，qwb并不打算把这些题全做完，
他想选总共道题来做，并且期望他能获得的分数尽可能的大，他准备选个不连续的长度为k的区间,
即。

解题思路：

前缀合加前缀最大值，数组用来存放，第个元素到第个元素的和，数组用来存放前个元素中，取个连续元素组成的区间和的最大值。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(i=a;i<=b;i++)
#define debug(a) cout<<#a<<":"<<a<<endl;
const ll INF=1e18+7;
const ll N=1e6+7;
const ll mod=1e9+7;
ll maxn,minn;
ll T,n,k;
ll dp1[N];
ll dp2[N];
ll arr[N];

int main(){
    cin>>T;
    while(T--){
        ll ans=0;
        cin>>n>>k;
        for(ll i=1;i<=n;i++){
            scanf("%lld",arr+i);
            if(i<=k){
                ans+=arr[i];
            }
        }
        dp1[k]=ans;
        for(ll i=k+1;i<=n;i++){
            dp1[i]=dp1[i-1]-arr[i-k]+arr[i];
        }
        dp2[k]=dp1[k];
        for(ll i=k+1;i<=n;i++){
            dp2[i]=max(dp2[i-1],dp1[i]);
        }
        ans=-INF;
        for(ll i=2*k;i<=n;i++){
            ans=max(ans,dp1[i]+dp2[i-k]);
        }
        cout<<ans<<endl;
    }

    return 0;
}