标题

由题意看可知需要求出两端不连续区间，同时使两个区间的和最大：

区间求和问题可以想到一个常用算法：前缀和。区间 [l,r][l,r] 的和可以用 sum_r-sum_{l-1}sum r ​ −sum l−1 ​ 方便地求出。

预处理序列的前缀和后，如何得知某个位置之前和之后的和最大的区间呢？我们可以使用线性 DPDP 求得。设 f1_if1 i ​ 表示位置 ii 之前的最大区间和，f2_if2 i ​ 表示位置 ii 之后的最大区间和。那么有：

f1_i=\maxf1 i ​ =max {f1_{i-1}f1 i−1 ​ ，sum_i-sum_{i-k}sum i ​ −sum i−k ​ } f2_i=\maxf2 i ​ =max {f2_{i+1}f2 i+1 ​ ，sum_{i+k-1}-sum_{i-1}sum i+k−1 ​ −sum i−1 ​ } 由于数据范围较大，需要开long longlonglong。注意 ff 数组初始化为负无穷。

时间复杂度：O(Tn)O(Tn)。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll a[2000005];

int main()
{
	ios::sync_with_stdio(0);
	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 sum=-1e18,ans=-1e18;
		for(int i=k;i+k<=n;i++)
		{
			sum=max(sum,a[i]-a[i-k]);
			ans=max(ans,sum+a[i+k]-a[i]);
		}
		
		cout<<ans<<endl;
	}
	
	return 0;
}