Void-7's

分治法 连续子数组的最大和

ysg

上次的“找出一个连续子数组最大和”的问题用的是一遍扫描的一般方法,如果用分治策略来解决的话,要怎么做呢?

分治策略中,我们递归地求解一个问题,在每一层递归中应用以下三步:

  1. Divide 将大的问题分解为多个子问题,问题规模缩小
  2. Conquer 递归地求解出子问题。只要子问题规模够小,这时停止递归并返回解
  3. Combine 将子问题地解进行合并,得到原来大的问题的解

按照以上步骤,对于连续子数组最大和的问题,我们可以:

  1. 将问题分解为三部分:求【数组左半部分的连续子数组最大和】、【右半部分的连续子数组最大和】、【跨越左右的连续子数组的最大和】
  2. 递归地求解出这三个子问题的解并返回:当递归进行到子问题规模只有一个数组项的时候(子数组的首尾索引相等),【数组左半部分的连续子数组最大和】=【右半部分的连续子数组最大和】=【跨越左右的连续子数组的最大和】=【该数组项的值】,这时候停止递归,直接返回数组值即可。
  3. 得到以上三个值之后对其进行比较,取最大值。

其中,对于【跨越左右的连续子数组的最大和】,因为中间不可能出现中断,我们只需要从数组的中间位置开始,分别向左和向右进行求和找最大值,得到两部分的和相加即可。

#include<iostream>
using namespace std;

//O(n)一般方法
int getMaxSubSum(int n,int *a){
    int max=a[0],sum=0;
    for(int i=0;i<n;i++){
        sum+=a[i];
        if(sum>max) max=sum;
        //当sum变成负数的时候会拖累后面的累加
        //所以直接重置,从下一个开始寻找最大和的连续子数组
        if(sum<0) sum=0;
    }
    return max;
}

//找到跨越左右的连续子数组最大和的函数
int getMidMaxSum(int l,int r,int *a){
    int mmax;int mid=(l+r)>>1;
    //左
    int lmax=a[mid],rmax=a[mid+1];
    int lsum=0,rsum=0;
    for(int i=mid;i>=l;i--){
        lsum+=a[i];
        if(lsum>lmax) lmax=lsum;
    }
    //右
    for(int i=mid+1;i<=r;i++){
        rsum+=a[i];
        if(rsum>rmax) rmax=rsum;
    }
    mmax=lmax+rmax;
    return mmax;
}

//分治法
int getMaxSubSum_d(int left,int right,int *a){
    int max=0;
    int mid=(left+right)>>1;
    if(left==right) return a[left];

    int lmax=getMaxSubSum_d(left,mid,a);
    int mmax=getMidMaxSum(left,right,a);
    int rmax=getMaxSubSum_d(mid+1,right,a);

    int tmp=lmax>rmax?lmax:rmax;
    max=tmp>mmax?tmp:mmax;
    return max;
}

int main(){
    int b[]={-1, -2, 3, -2, 11};
    cout<<getMaxSubSum(5,b)<<endl;
    cout<<getMaxSubSum_d(0,4,b)<<endl;
    int a[]={0},c[]={-2,4,9};
    cout<<getMaxSubSum(1,a)<<endl;
    cout<<getMaxSubSum_d(0,0,a)<<endl;
    cout<<getMaxSubSum(3,c)<<endl;
    cout<<getMaxSubSum_d(0,2,c)<<endl;
    return 0;
}
/*
    output:
    12
    12
    0
    0
    13
    13
*/