数学考试~前缀和（尺取）

链接：https://www.nowcoder.com/acm/contest/96/H
来源：牛客网

题目描述

今天qwb要参加一个数学考试，这套试卷一共有n道题，每道题qwb能获得的分数为ai，qwb并不打算把这些题全做完，
他想选总共2k道题来做，并且期望他能获得的分数尽可能的大，他准备选2个不连续的长度为k的区间,
即[L,L+1,L+2,....,L+k-1]，[R,R+1,R+2,...,R+k-1]（R >= L+k）。

输入描述:

第一行一个整数T（T<=10）,代表有T组数据
接下来一行两个整数n,k,(1<=n<=200,000),(1<=k,2k <= n)
接下来一行n个整数a1,a2,...,an，（-100,000<=ai<=100,000）

输出描述:

输出一个整数，qwb能获得的最大分数

示例1

输入

2
6 3
1 1 1 1 1 1
8 2
-1 0 2 -1 -1 2 3 -1

输出

6
7

沉着冷静 认真分析 这题的复杂度用O(n)就可以过了，处理一下就好
注意初始化ans的时候要足够小，一开始一直WA这里

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
long long sum[2 * maxn], a[2 * maxn], pre[2 * maxn], premax[2 * maxn];
int main() {
    int n, k, t;
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &k);
        sum[0] = 0;
        for (int i = 1 ; i <= n ; i++) {
            scanf("%lld", &a[i]);
            sum[i] = sum[i - 1] + a[i];
        }
        premax[0] = -999999999999;
        for (int i = 1 ; i <= n - k + 1 ; i++ ) {
            pre[i] = sum[k + i - 1] - sum[i - 1];
            premax[i] = max(pre[i], premax[i - 1]);
        }
        long long ans = -999999999999999;
        for (int i = n - k + 1 ; i >= k  ; i--  ) {
            ans = max(ans, pre[i] + premax[i - k]);
        }
        printf("%lld
", ans);
    }
    return 0;
}