首页 > 其他 > 详细

最大子段和

时间:2020-06-05 10:54:31      阅读:43      评论:0      收藏:0      [点我收藏+]

最大子段和模型

  • 给定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)\)

        • 显然,如果\(f[i-1]+a[i]<0\) 直接置空,大于零,区间还有成长的空间。
        • 最终结果为:\(ans=max(ans,f[i])\ 0< i\le 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 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;
        }
        
    • 方法三:分治

      • 通过分治的思想求最大子段和,将数组分平均分为两个部分,则最大子段和会存在于三种情况下:

        1. 最大子段和出现在左端
        2. 最大子段和出现在右端
        3. 最大子段和横跨在左右段 通过比较大小得到最大子段和
      • 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;
        }
        
  • 我们对问题进行扩展,如果对序列有两种操作:

    1. 修改序列的某个元素的值
    2. 查询序列\([l,r]\)的区间和。
  • 题目模型见P4513 小白逛公园

  • 分析:

    • 单点修改,区间查询显然要用线段树。

    • 类似上面分治,区间最大字段和有三种情况:

      1. 最大子段和在左子树。
      2. 最大子段和在右子树。
      3. 左子树的最大后缀和+右子树的最大前缀和。
    • 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

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!