maximum Subarray

题目描述

n个数的序列a，选择k个数+x,其余数-x，求做完操作后的最大子段和。

最大子段和模板

`for(int i = 1; i <= n; i ++ ) dp[i] = max(dp[i - 1] + a[i], a[i]); 

思路

我们发现x=0时问题就是普通的最大子段和问题。

当x≠0时

由于k很小（k≤20），我们可以暴力枚举+x或-x的情况，然后再求最大子段和。

当x>0时

+x的部分变大，如果要让子段和最大，+x的部分自然要在子段中，贪心地考虑，+x的部分应尽可能也是连续的，才能尽可能地被子段包含。所以我们枚举+x段的位置，然后求最大子段和。

for(int i=0;i<=n+2;i++)pre[i]=-inf;
			for(int i=1;i<=n;i++)pre[i]=max(pre[i-1]+a[i]-x,a[i]-x);
			for(int i=1;i<=n-k+1;i++){
				for(int j=0;j<=k+1;j++)dp[i]=-inf;
				dp[0]=pre[i-1];
				for(int j=1;j<=k;j++){
					dp[j]=max(dp[j-1]+a[i+j-1]+x,a[i+j-1]+x);
					ans=max(ans,dp[j]);
				}
			}
			cout<<ans<<endl;

这里我们预先处理了-x的最大子段和，便于我们暴力维护+x的子段和。

当x<0时

-x的部分变大，为了尽量让-x的部分在子段中，即-x的部分连续，我们可以把+x的部分尽量放在两边，也就是说我们可以暴力枚举两端的端点，然后求最大子段和。

for(int l=0;l<=k;l++){
				int r=n-(k-l)+1;
				for(int i=1;i<=n;i++){
					if(i<=l||i>=r)dp[i]=max(dp[i-1]+a[i]+x,a[i]+x);
					else dp[i]=max(dp[i-1]+a[i]-x,a[i]-x);
					ans=max(dp[i],ans);
				}
			}

完整代码

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ls 2*x
#define rs 2*x+1
#define mid ((l+r)/2)
#define pii pair<int,int>
#define fi first
#define se second
#define int long long
const int N=1e6+10;
const int mod=1e9+7;
const int inf=1e18;
int a[N],dp[N],pre[N];
signed main(){
	int T;
	cin>>T;
	while(T--){
		
		int n,k,x;
		cin>>n>>k>>x;for(int i=0;i<=n+2;i++)dp[i]=-inf;
		int ans=0;
		for(int i=1;i<=n;i++){
			cin>>a[i];
		}
		if(k==0){
			for(int i=1;i<=n;i++){
				dp[i]=max(dp[i-1]+a[i]-x,a[i]-x);
				ans=max(dp[i],ans);
			}
			cout<<ans<<endl;
		}else if(x>=0){
			for(int i=0;i<=n+2;i++)pre[i]=-inf;
			for(int i=1;i<=n;i++)pre[i]=max(pre[i-1]+a[i]-x,a[i]-x);
			for(int i=1;i<=n-k+1;i++){
				for(int j=0;j<=k+1;j++)dp[i]=-inf;
				dp[0]=pre[i-1];
				for(int j=1;j<=k;j++){
					dp[j]=max(dp[j-1]+a[i+j-1]+x,a[i+j-1]+x);
					ans=max(ans,dp[j]);
				}
			}
			cout<<ans<<endl;
		}else{
			for(int l=0;l<=k;l++){
				int r=n-(k-l)+1;
				for(int i=1;i<=n;i++){
					if(i<=l||i>=r)dp[i]=max(dp[i-1]+a[i]+x,a[i]+x);
					else dp[i]=max(dp[i-1]+a[i]-x,a[i]-x);
					ans=max(dp[i],ans);
				}
			}
			cout<<ans<<endl;
		}
	} 
	return 0;
}