题目描述

今天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）。

解题思路

前缀和思想。
先在数据输入的时候预处理前缀和，那么给定的图片说明 开始连续k个数字和就是sum[l+k-1]-sum[l-1]。
那么我们枚举第一个区间终点i，长度为k的前缀和，可以再去从终点向后枚举k个前缀和，取到最大答案。
这样的时间复杂度是图片说明 数据规模应该是图片说明 。
在思考思考优化的办法，我们有必要每次都去枚举后面全部的取值么？好像不需要，因为我们前面是通过枚举终点一步步向后，那么如果我们找到了终点前的题目最大k项和，加上终点后的sum[i+k]-sum[i]取最大，就行了，想想为什么，因为我们的i是递推向后，如果终点前k项和不变，我们终点后的sum[i+k]-sum[i]可以取遍所有组合，如果终点前k项和更新了，后面也可以取遍终点所有组合。
说简单点，就是枚举分割点i，记录i前面（包括i在内）的最大k项前缀和，再计算i后面k项的和，更新答案。
时间复杂度图片说明

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43628068&returnHomeType=1&uid=919749006

Code

#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;

inline int read() {
    int s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}

const int N = 2e5 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll sum[N]; // 最大 2e5个1e5和2e10 int爆掉了，开到ll来

int main() {
    int T = read();
    while (T--) {
        int n = read(), m = read();
        //输入数据并且处理成前缀和
        for (int i = 1; i <= n; ++i)
            sum[i] = read(), sum[i] += sum[i - 1];
        ll maxi = -INF, ans = -INF; //因为区间存在负数，所以初始化要负无穷大
        for (int i = m; i + m <= n; ++i) { //从m开始枚举分割点，n-m+1是后面半段的最大位置起始位置
            maxi = max(maxi, sum[i] - sum[i - m]); //求i前面m个元素的最大前缀
            ans = max(ans, maxi + sum[i + m] - sum[i]); //maxi加上i后面m个元素的最大前缀和
        }
        printf("%lld\n", ans);
    }
    return  0;
}