给定n
个整数(可能为负数)组成的序列\(a_1,a_2,...,a_n\) ,求该序列如:\(a_{i}+a_{i+1}+...+a_j\ i\le j\) 的子段和的最大值。当所给的整数均为负数时定义子段和为0
。
即:\(ans=max(0,\sum_{i=l}^r a_i),\ (1\le l\le r\le n\le 10^7)\) 。
分析:
方法一:前缀和
很容易想到 \(O(n^2)\) 枚举所有区间\([l,r]\) ,\(O(n)\) 的效率求出区间和。总时间效率为\(O(n^3)\) 。
维护序列的前缀和,利用差分思想,很容易把区间和优化到\(O(1)\)。总时间效率为\(O(n^2)\)。
\(n\) 高达千万,要想在 \(1s\) 内解决问题,需要把时间效率降到\(O(n)\) 级别。
假设区间\([l,r]\),区间和\(sum=sum[r]-sum[l-1]\)我们固定左边界\(r\),从\(1\sim r\) 中找到前缀和最小的\(l\)。
所以我们只需要\(O(n)\) 去遍历序列,遍历的同时维护一下已遍历区间最小前缀和即可。
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e7+5,maxm=1e5+5;
const LL Inf=0x3f3f3f3f3f3f3f3f;
LL a[maxn],sum[maxn];
int n;
void Solve(){
srand(time(0));
scanf("%d",&n);
LL Min=Inf,ans=0;
for(int i=1;i<=n;++i){
a[i]=rand()%10000-5000;
sum[i]=sum[i-1]+a[i];
Min=std::min(Min,sum[i]);
ans=std::max(ans,sum[i]-Min);
}
printf("%lld\n",ans);
}
int main(){
Solve();
return 0;
}
方法二:动态规划
定义状态f[i]
?表示以 i
结尾的最大子段和(可以为空)。
转移方程:\(f[i]=max(f[i-1]+a[i],0)\)
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e7+5,maxm=1e5+5;
const LL Inf=0x3f3f3f3f3f3f3f3f;
LL f[maxn],a[maxn],ans;
int n;
void Solve(){
srand(time(0));
scanf("%d",&n);
for(int i=1;i<=n;++i){
a[i]=rand()%10000-5000;
f[i]=std::max(f[i-1]+a[i],0LL);
ans=std::max(ans,f[i]);
}
printf("%lld\n",ans);
}
int main(){
Solve();
return 0;
}
方法三:分治
通过分治的思想求最大子段和,将数组分平均分为两个部分,则最大子段和会存在于三种情况下:
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=1e7+5,maxm=1e5+5;
const LL Inf=0x3f3f3f3f3f3f3f3f;
LL a[maxn];
int n;
LL MaxSum(int l,int r){
LL sum=0,midSum=0,leftSum=0,rightSum=0;
if(l==r)
sum=a[l];
else{
int mid=(l+r)/2;
LL leftSum=MaxSum(l,mid); //情况1,最大字段和全部取左边元素
LL rightSum=MaxSum(mid+1,r);//情况2,最大字段和全部取右边元素
LL tot=0,sumleft=0,sumright=0; //情况3 最大子段和横跨中间
for(int i=mid;i>=l;i--){ //求出从中间a[mid]到左边的最大和
tot+=a[i];
if(tot>sumleft) sumleft=tot;
}
tot=0;
for(int i=mid+1;i<=r;++i){ //求出从中间a[mid+1]到右边的最大和
tot+=a[i];
if(tot>sumright) sumright=tot;
}
LL midSum=sumleft+sumright; //横跨中间的最大字段和为
sum=std::max(midSum,std::max(leftSum,rightSum));//取三者较大者
}
return sum;
}
void Solve(){
srand(time(0));
scanf("%d",&n);
for(int i=1;i<=n;++i){
a[i]=rand()%10000-5000;
}
printf("%lld\n",ans);
printf("%lld\n",MaxSum(1,n));
}
int main(){
Solve();
return 0;
}
我们对问题进行扩展,如果对序列有两种操作:
题目模型见P4513 小白逛公园
分析:
单点修改,区间查询显然要用线段树。
类似上面分治,区间最大字段和有三种情况:
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e5+10;
#define lson l,mid,(rt<<1)
#define rson mid+1,r,(rt<<1|1)
struct Tree{
int presum,sufsum,sub,sum;//presum为当前区间最大前缀和,sufsum为当前区间最大后缀和,sub为当前区间最大子段和,sum为当前区间的和
}tree[maxn<<2];
Tree pushup(Tree l,Tree r){//合并左右两区间
Tree rt;
rt.presum=max(l.presum,l.sum+r.presum);//当前区间的最大前缀和:左子树的最大前缀和 or 左子树的和+右子树的最大前缀和
rt.sufsum=max(r.sufsum,r.sum+l.sufsum);//当前区间的最大后缀和:右子树的最大后缀和 or 右子树的和+左子树的最大后缀和
rt.sub=max(max(l.sub,r.sub),l.sufsum+r.presum);//当前区间的最大子段和:左子树的最大子段和 or 右子树的最大子段和 or 左子树的最大后缀和+右子树的最大前缀和
rt.sum=l.sum+r.sum;//当前区间的和:左子树的和+右子树的和
return rt;
}
void build(int l,int r,int rt){
if(l==r){
scanf("%d",&tree[rt].sum);
tree[rt].presum=tree[rt].sufsum=tree[rt].sub=tree[rt].sum;
return ;
}
int mid=(l+r)>>1;
build(lson);
build(rson);
tree[rt]=pushup(tree[rt<<1],tree[rt<<1|1]);
}
void update(int pos,int w,int l,int r,int rt){//把pos个元素修改成值w
if(l==r){
tree[rt].presum=tree[rt].sufsum=tree[rt].sub=tree[rt].sum=w;
return ;
}
int mid=(l+r)>>1;
if(pos<=mid) update(pos,w,lson);
if(pos> mid) update(pos,w,rson);
tree[rt]=pushup(tree[rt<<1],tree[rt<<1|1]);
}
Tree query(int L,int R,int l,int r,int rt){
if(L<=l&&r<=R)
return tree[rt];
int mid=(l+r)>>1;
Tree ret,lret,rret;
int flag1=0,flag2=0;//flag1标记区间[L,R]是否在rt的左子树,flag2右子树
if(L<=mid) {lret=query(L,R,lson);flag1=1;}
if(R> mid) {rret=query(L,R,rson);flag2=1;}
if(flag1&&flag2) ret=pushup(lret,rret);//左右子树均有就合并计算
else if(flag1) ret=lret;//只在左子树
else if(flag2) ret=rret;//只在右子树
return ret;
}
void Solve(){
int n,m;scanf("%d%d",&n,&m);
build(1,n,1);
for(int i=1;i<=m;i++){
int op;
scanf("%d",&op);
if(op==1){
int l,r;
scanf("%d%d",&l,&r);
if(l>r) swap(l,r);
Tree ans=query(l,r,1,n,1);
printf("%d\n",ans.sub);
}
else{
int p,s;
scanf("%d%d",&p,&s);
update(p,s,1,n,1);
}
}
}
int main(){
Solve();
return 0;
}
原文:https://www.cnblogs.com/hbhszxyb/p/13047611.html