前缀和+dp

• 利用前缀和思想 以及DP
  首先利用前缀和求出dp数组 dp[i] 代表 i到n 这个区间内 长度为k 的序列的和的最大值 然后再依次枚举 从k 到 n- k 区间内的 长度为 k的区间的最大值 也就是 sum[i]-sum[i-k] 然后再加上 i 到 这个区间内的最大值 每次取最大值
  主要知识点 前缀和 ： sum[i] = a1+a2+.....+a[i] 求[ l , r ]区间内的和的操作 为 sum[r] - sum [l - 1]
  推导如下
  sum[r] = a1 + a2 + a3 + ......+ a[r]
  sum[l - 1 ] =a1 + a2 + a3 +... a[l -1 ]
  sum [ r ]-sum[ r - 1 ] = a(l) + a(l+1) +... a(r)

  #include<bits/stdc++.h>
  using namespace std;
  const int N = 200000 + 10;
  typedef long long ll;
  ll a[N] ,sum[N] ,dp[N];
  int n,k;
  void solve()
  {
    scanf("%d %d",&n,&k);
    for(int i = 1 ; i <= n ;i +=1)
    {
        scanf("%lld",&a[i]);
        sum[i] = sum [i - 1] + a[i];
    }
    // dp[i] 代表   i 到 n   区间类似于[i-k,i]最大的和
    ll ma = LONG_LONG_MIN;
    for(int i = n ; i >= k ; i --){
        ma = max(ma,sum[i] - sum[i - k]);
        dp[i] = ma;
    }
    ll res = LONG_LONG_MIN;
    for(int i = k ; i <= n - k ; i ++){
        res = max(res , sum [i] - sum[i - k] +dp[i + k]);
    }
    printf("%lld\n",res);
  }
  int main()
  {
    int T;
    //freopen("in.txt","r",stdin);
    scanf("%d",&T);
    while(T--){
        solve();
    }
    return 0;
  }
  

```