soltion
我们可以预处理出一个L数组,其中表示以i为右端点的长度为k的区间和。然后预处理一个数组表示以i为左端点的长度为k的区间和。这两个数组都可以通过预处理前缀和然后相减的方法得到。即:记为区间的数字和,那么区间的数字和就是
然后考虑如何找到两个最大的不相交的长度为k的区间,很容易想到对做一个前缀最大值,对做一个后缀最大值。然后枚举一下左边区间的右端点,找到右边区间中的最大值就可以保证两个区间不相交了。
单组数据复杂度
注意因为输入有负数,所以赋的初值应为极小值而不是0.
code
/* * @Author: wxyww * @Date: 2020-04-02 14:08:41 * @Last Modified time: 2020-04-02 14:16:44 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<algorithm> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; const int N = 200010; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } ll a[N],L[N],R[N]; int main() { int T = read(); while(T--) { int n = read(),k = read(); memset(L,-0x3f,sizeof(L)); memset(R,-0x3f,sizeof(R)); for(int i = 1;i <= n;++i) a[i] = a[i - 1] + read(); for(int i = k;i <= n;++i) L[i] = max(L[i - 1],a[i] - a[i - k]); for(int i = n - k + 1;i >= 1;--i) R[i] = max(R[i + 1],a[i + k - 1] - a[i - 1]); ll ans = -1e15; for(int i = k;i + k <= n;++i) ans = max(ans,L[i] + R[i + 1]); cout<<ans<<endl; } return 0; }