NC15553 数学考试

数学考试

https://ac.nowcoder.com/acm/problem/15553

给定一个数组arr[ ](有正有负),选择两段子数组(子数组长度等于K)

求和最大的两段子数组,打印和

• 先求前缀和

状态表示:

​ $lef\left[i\right]$        lef[i]表示 $i$i的左边的长度为K的子数组最大和(包括 $i$i)

​ $rig\left[i\right]$        rig[i]表示 $i$i的右边的长度为K的子数组最大和(包括 $i$i)

转移方程:

​ $lef\left[i\right]=max\left(lef\right[i-1],sum[i]-sum[i-K\left]\right)$        lef[i]=max(lef[i−1],sum[i]−sum[i−K])

​ $rig\left[i\right]=max\left(rig\right[i+1],rig[i+K-1]-sum[i-1\left]\right)$        rig[i]=max(rig[i+1],rig[i+K−1]−sum[i−1])

​ $ans=max(ans,lef[i]+rig[i+1\left]\right)$        ans=max(ans,lef[i]+rig[i+1])
初始状态
$lef\left[\right]和rig\left[\right]应该初始化为最小,因为有负数$        lef[ ]和rig[ ]应该初始化为最小,因为有负数
$memset(lef,-0x7f,sizeof(lef\left)\right)$        memset(lef,−0x7f,sizeof(lef))

#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif


#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>
#define MAXN ((int)2e5+7)
#define ll long long 
#define int long long 
#define INF (0x7f7f7f7f)
#define QAQ (0)

using namespace std;

#ifdef debug
#define show(x...) \ do { \ cout << "\033[31;1m " << #x << " -> "; \ err(x); \ } while (0)
void err() { cout << "\033[39;0m" << endl; }
#endif

template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }

//从一个数组里选两段长度为K的子数组a1[],a2[],要求sum_a1+sum_a2最大
int n, m, Q, K, a[MAXN], sum[MAXN];
ll lef[MAXN]; //表示位置i左边长度为K的子数组(包括i)的最大和
ll rig[MAXN]; //表示位置i右边长度为K的子数组(包括i)的最大和

signed main() {
#ifdef debug
	freopen("test", "r", stdin);
	clock_t stime = clock();
#endif
	scanf("%lld ", &Q);
	while(Q--) {
		scanf("%lld %lld ", &n, &K);
		
		memset(sum, 0, sizeof(sum));
		memset(lef, -0x7f, sizeof(lef));
		memset(rig, -0x7f, sizeof(rig));
	
		for(int i=1; i<=n; i++) 
			scanf("%lld ", a+i), sum[i]=sum[i-1]+a[i];

		for(int i=K; i<=n-K; i++) 
			lef[i] = max(lef[i-1], (sum[i]-sum[i-K]));

		for(int i=n-K+1; i>=K+1; i--) 
			rig[i] = max(rig[i+1], (sum[i+K-1]-sum[i-1]));

		//forarr(lef, 1, n, "lef");
		//forarr(rig, 1, n, "rig");
		int ans = -1e18;
		for(int i=K; i<=n-K; i++) 
			ans = max(ans, lef[i]+rig[i+1]);
		printf("%lld \n", ans);
	}




#ifdef debug
	clock_t etime = clock();
	printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
	return 0;
}