数学考试

题目链接：数学考试
题目大意：给定长为n的数组和k，从数组中任意选择不相交的长度为k的两段，求其和的最大值。

解题思路：预处理出从[k+1,n]区间内的值最大的长度为k的子串的值，再顺序遍历数组将以当前下标id为右边界的长为k的区间值求出后，加上预处理出[id+1,n]的最大值。这就是当前下标可能取到的最大值。

注意事项：需要开long long,且有负数的分数，多组输入需要初始化

代码：

#include<stdio.h>
#include<algorithm>
using namespace std;
#define ll long long
const int N = 2e5+5;
ll a[N],b[N];
int n,k;
void solve()
{scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){scanf("%lld",&a[i]);a[i] += a[i-1];//前缀和}b[n-k+1] = -1e12;//负数的分数for(int i=n-k+1;i>k;i--)//求出[i,n]的第二个区间的最大值{ll num = a[i+k-1]-a[i-1];//以当前下标为右边界的长度为k的区间的值b[i] = max(b[i+1],num);//和之前的最大值比较}ll ans = -1e12;for(int i=k;i<=n-k;i++){ll num = a[i]-a[i-k];//枚举第一个区间的右边界ans = max(ans,num+b[i+1]);//加上最大的第二区间，和之前的答案比较}printf("%lld\n",ans);
}
int main()
{int T;scanf("%d",&T);while(T--)solve();return 0;
}