学步园

DP[i]表示以i结尾长度大于等于m的最大和。

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=1000000+5;
int a[maxn],dp[maxn];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m,sum=0;
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++){///dp[i]初始化为i结尾，长度为m的和
            scanf("%d",&a[i]);
            if(i<m) sum+=a[i],dp[i]=sum;
            else{
                sum=sum-a[i-m]+a[i];
                dp[i]=sum;
            }
        }
        int Max=dp[m-1];
        for(int i=m;i<n;i++)
        {
            dp[i]=max(dp[i-1]+a[i],dp[i]);
            Max=max(Max,dp[i]);
        }
        cout<<Max<<endl;
    }
    return 0;
}