数学考试

题目分析：

1.连续区间的求和，可以用暴力去枚举，但是最好的方法就是采用前缀和来优化sum[i]=sum[i−1]+a[i]，如果我们要求[l,r]区间的和直接用sum[r]−sum[l−1],前缀和能极大的降低程序的时间复杂度
2.求最优值得话我们就需要用动态规划的思想，在选与不选之间，选一个最优的，我们把整个区间分为两半，以i为分界线，分别求出两段区间的最优值，相加就是所需的答案
3.由于数据比较大，所以我们需要用long long来定义变量和数组
4.答案可能出现负数，为了避免不必要的麻烦我们就把ans初始化为一个很小很小的数字

AC代码

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1e6 + 10;
typedef long long ll;
ll w[maxn], sum[maxn], a[maxn], b[maxn];
int main()
{
   
    ll t, n, k, ans;
    scanf("%lld", &t);
    while (t--)
    {
   
        ans = -1e18;
        memset(a, -inf, sizeof(a));
        memset(b, -inf, sizeof(b));
        scanf("%lld%lld", &n, &k);
        for (int i = 1; i <= n; ++i)
        {
   
            scanf("%lld", &w[i]);
            sum[i] = sum[i - 1] + w[i]; //求前缀和
        }
        for (int i = k; i <= n - k; ++i)
            a[i] = max(sum[i] - sum[i - k], a[i - 1]); //求i的左边
        for (int i = n - k + 1; i >= k + 1; --i)
            b[i] = max(sum[i + k - 1] - sum[i - 1], b[i + 1]); //求i的右边
        for (int i = k; i <= n - k; ++i)
            ans = max(ans, a[i] + b[i + 1]); //至于为什么要从k开始因为我们求的区间的长度就是k，如果从小于k开始那么就会越界了
        printf("%lld\n", ans);
    }
    return 0;
}