牛客-数学考试

原题链接：https://ac.nowcoder.com/acm/problem/15553

题目

今天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能获得的最大分数

分析

首先预判下该题的时间复杂度。n<=200,000,极限数据下n²会TLE，所以可推断出时间复杂度至多为nlogn量级。再看题划重点——选2个不连续的长度为k的区间，即：“求两个固定长度的最大区间和”，那么很自然想到用前缀和。

首先，我们可以从左往右找到一个长度为k的最大区间和，记作：Ma。

所以，

$Ma=max\left\{Ma,a[i]-a[i-k]\right\}$

对于求Ma过程中扫描过的每个a[i],我们都可以找到一个与之对应的区间和a[i+k]-a[i]。

所以要求的两个不连续最大区间和，就等于Ma+**a[i+k]-a[i]**的最大值,即：

$ans=max\left\{ans,Ma+a[i+k]-a[i]\right\}$

这个算法的时间复杂度是O(n)，在接受范围之内。

最后需要注意的是，极限数据答案为2⁵×10⁵>2³¹-1，即：会爆int。所以数组a，第一个区间最大和Ma和最后答案ans,都要开成long long。

代码

#include<iostream>
using namespace std;
const int N=1e6;
typedef long long ll;
ll a[N];
int main(){
	int T;
	cin>>T;
	while(T--){
		int n,k;
		cin>>n>>k;
		for(int i=1;i<=n;i++)cin>>a[i],a[i]+=a[i-1];
		
		ll Ma=-1e10,ans=-1e10;
		for(int i=k;i+k<=n;i++){
			Ma=max(Ma,a[i]-a[i-k]);
			ans=max(ans,Ma+a[i+k]-a[i]);
		}
		cout<<ans<<endl;
	}	
	return 0;
}

---