数学考试~前缀和（尺取）
链接：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）。
他想选总共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这里
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn = 1e5 + 10; 4 long long sum[2 * maxn], a[2 * maxn], pre[2 * maxn], premax[2 * maxn]; 5 int main() { 6 int n, k, t; 7 scanf("%d", &t); 8 while(t--) { 9 scanf("%d%d", &n, &k); 10 sum[0] = 0; 11 for (int i = 1 ; i <= n ; i++) { 12 scanf("%lld", &a[i]); 13 sum[i] = sum[i - 1] + a[i]; 14 } 15 premax[0] = -999999999999; 16 for (int i = 1 ; i <= n - k + 1 ; i++ ) { 17 pre[i] = sum[k + i - 1] - sum[i - 1]; 18 premax[i] = max(pre[i], premax[i - 1]); 19 } 20 long long ans = -999999999999999; 21 for (int i = n - k + 1 ; i >= k ; i-- ) { 22 ans = max(ans, pre[i] + premax[i - k]); 23 } 24 printf("%lld ", ans); 25 } 26 return 0; 27 }