数学考试

题目链接：
https://ac.nowcoder.com/acm/problem/15553

思路:
区间求和，这题用前缀和+dp写真是绝了，神奇的解题方法又增加了（萌新瑟瑟发抖）。

解题代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <map>
using namespace std;
const long long N = 2e5 + 7;
typedef long long ll;
ll sum[N],f1[N],f2[N];
int main()
{
    int t ;
    cin >> t;
    while(t--)
    {
        int n,k,a;
        ll num = -1e12;
        cin >> n >> k;
        memset(sum , 0 , sizeof(sum) );
        for(int i = 1;i <= n;i++)
        {
            cin >> a;
            sum[i] += a + sum[i-1];
        }
        memset(f1 , -0x3f3f3f3f , sizeof(f1) );
        memset(f2 , -0x3f3f3f3f , sizeof(f2) );
        for(int i = k;i <= n - k;i++)
            f1[i] = max(f1[i-1] , sum[i]-sum[i-k] );
        for(int i = n-k; i >= k;i--)
            f2[i] = max(f2[i+1] , sum[i+k]-sum[i] );
        for(int i = k;i <= n - k;i++)
        {
            num = max(num,f1[i] + f2[i]);
        }
        cout << num << endl;
    }

    return 0;
}