区间最大子段和问题

问题

给定一个数列

a_1,a_2,a_3,...,a_n

有

m

次询问，每次询问给你两个数

l,r

你需要求出

a_l \sim a_r

的最大子段和

做法

1.暴力统计

对于每一个区间

[l,r]

，枚举左端点和右端点，求所有区间的最大值，复杂度为

O(mn^2)

2.动态规划

我们可以一次性算出所有区间的最大子段和，然后直接输出答案
规定：

$ls$ : 表示紧靠左端点的子段的最大和
$rs$ : 表示紧靠右端点的子段的最大和
$ms$ : 表示最大子段和
$s$ : 表示区间子段和

假设一个区间为

[l,r]

,将它分成两段，两个子段的信息已经处理完成
显然有：

s=s_l+s_r

ls

要么选左区间的

ls

，要么选把左区间选完在加右区间的

ls

ls=max(ls_l,s_l+ls_r)

右区间同理

rs=max(rs_r,s_r+rs_l)

ms

要么选左区间

ms

，要么选右区间

ms

，要么左区间的

rs

加右区间的

ls

ms=max(ms_l,ms_r,rs_l+ls_r)

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,m,val[N];
long long ls[N][N],rs[N][N],ms[N][N],s[N][N];
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>val[i];
	for(int i=1;i<=n;i++) ls[i][i]=rs[i][i]=ms[i][i]=s[i][i]=val[i];
	for(int len=2;len<=n;len++)
	{
		for(int l=1;l+len-1<=n;l++)
		{
			int r=l+len-1;
			int mid=(l+r)>>1;
			s[l][r]=s[l][mid]+s[mid+1][r];
			ls[l][r]=max(ls[l][mid],ls[mid+1][r]+s[l][mid]);
			rs[l][r]=max(rs[mid+1][r],rs[l][mid]+s[mid+1][r]);
			ms[l][r]=max(ls[mid+1][r]+ls[l][mid],max(ms[l][mid],ms[mid+1][r]));
		}
	}
	cin>>m;
	int l,r;
	while(m--)
	{
		cin>>l>>r;
		cout<<ms[l][r]<<"\n";
	}
	return 0;
}

复杂度为

O(n+m)

线段树

例题：SP1716
若数列

a

会修改，动态规划就不能求解
这时我们可以用线段树来维护，可单点修改、区间查询

CPP

#include<bits/stdc++.h>
#define ll long long
#define lc rt<<1
#define rc rt<<1|1
#define mid ((l+r)>>1)
using namespace std;
const int N=1e5+10;
const ll inf=2e18;
int n,m;
struct node
{
	ll ls,rs;
	ll ms;
	ll s;
}tr[4*N];
void pushup(int rt)
{
	tr[rt].s=tr[lc].s+tr[rc].s;
	tr[rt].ls=max(tr[lc].ls,tr[rc].ls+tr[lc].s);
	tr[rt].rs=max(tr[rc].rs,tr[lc].rs+tr[rc].s);
	tr[rt].ms=max(tr[lc].rs+tr[rc].ls,max(tr[lc].ms,tr[rc].ms));
	return ;
}
void build(int rt,int l,int r)
{
	if(l==r)
	{
		cin>>tr[rt].s;
		tr[rt].ls=tr[rt].rs=tr[rt].ms=tr[rt].s;
		return ;
	}
	build(lc,l,mid);
	build(rc,mid+1,r);
	pushup(rt);
	return ;
}
void update(int rt,int l,int r,int pos,int val)
{
	if(l==r)
	{
		tr[rt].s=tr[rt].ls=tr[rt].rs=tr[rt].ms=val;
		return ;
	}
	if(pos<=mid) update(lc,l,mid,pos,val);
	else update(rc,mid+1,r,pos,val);
	pushup(rt);
	return ;
}
node query(int rt,int l,int r,int L,int R)
{
	if(L<=l&&r<=R) return tr[rt];
	node x,y,w;
	if(R<=mid) w=query(lc,l,mid,L,R);
	else if(L>mid) w=query(rc,mid+1,r,L,R);
	else
	{
		x=query(lc,l,mid,L,mid);
		y=query(rc,mid+1,r,mid+1,R);
		w.s=x.s+y.s;
		w.ls=max(x.ls,x.s+y.ls);
		w.rs=max(y.rs,y.s+x.rs);
		w.ms=max(x.rs+y.ls,max(x.ms,y.ms));
	}
	return w;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	build(1,1,n);
	cin>>m;
	int opt,l,r,pos,val;
	while(m--)
	{
		cin>>opt;
		if(opt==0)
		{
			cin>>pos>>val;
			update(1,1,n,pos,val);
		}
		else
		{
			cin>>l>>r;
			node ans=query(1,1,n,l,r);
			cout<<ans.ms<<"\n";
		}
	}
	return 0;
}

复杂度为

O(n+mlogn)

区间最大子段和问题

文章操作

问题

做法

1.暴力统计

2.动态规划

线段树

相关推荐

评论

区间最大子段和问题