求大佬看看我的思路哪里不对
根据题意我们知道,不能选两个有交集的区间,我们只需要先选一遍最大的长度为k的区间,然后再遍历一遍选择大小为第二大的区间。
选择第二大的区间我的方案是不与上一个选出来的产生交集
// Problem: 数学考试
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/problem/15553
// Memory Limit: 65536 MB
// Time Limit: 2000 ms
// Code by: ING__
//
// Powered by CP Editor (https://cpeditor.org)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <sstream>
#define ll long long
#define re return
#define Endl "\n"
#define endl "\n"
using namespace std;
typedef pair<int, int> PII;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int T;
int n;
int k;
ll s[200010];
int main(){
cin >> T;
while(T--){
cin >> n >> k;
memset(s, 0, sizeof(s));
for(int i = 1; i <= n; i++){
ll x;
cin >> x;
s[i] = s[i - 1] + x;
}
// int ans = 0;
// 选取第一大的区间
ll maxa = -1e19;
int r1;
for(int i = k; i <= n; i++){
if(maxa < s[i] - s[i - k]){
maxa = s[i] - s[i - k];
r1 = i;
}
}
// 选取第二大的区间
ll maxb = -1e19;
for(int i = k; i <= n; i++){
if(i >= r1 - k + 1 && i - k + 1 <= r1) continue;
if(maxb < s[i] - s[i - k]){
maxb = s[i] - s[i - k];
}
}
cout << maxa + maxb << endl;
}
re 0;
} 