数学考试dp解法

题目大意：

有一个长度为n的数列，要求在这个数列中选2个不相交且长度都为k的区间，求这两个区间中数字和最大的值

算法过程

A[i]表示长度为k且以i为最后一个元素的这个区间元素值的和
dp[i]表示选择的第二个区间以第i个元素结尾所求和的最大值
维护一个tmp，表示在前i-k个元素中长度为k的区间和最大值
那么状态转移方程为

dp[i]=tmp+A[i]

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,int> P;
const int INF=0x3f3f3f3f;
const LL LINF=0x3f3f3f3f3f3f;
const int MAX_N=2e5+20;
const LL MOD=1e9+7;
int n,k;
LL a[MAX_N];
LL A[MAX_N];//A[i]表示长度为k且以i为最后一个元素的这个区间元素值的和
LL dp[MAX_N];
int T;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++){
            scanf("%lld",&a[i]);
        }
        LL sum=0;
        for(int i=1;i<=k-1;i++){
            A[i]=-1;
            sum+=a[i];
        }
        for(int i=k;i<=n;i++){
            sum+=a[i];
            A[i]=sum;
            sum-=a[i-k+1];
        }
        LL tmp=A[k];
        LL ans=-LINF;//注意可能是负值
        for(int i=2*k;i<=n;i++){
            dp[i]=A[i]+tmp;
            tmp=max(tmp,A[i-k+1]);
            ans=max(dp[i],ans);
        }
        printf("%lld\n",ans);
    }
}