最大子数组问题

曾经终败给现在 2022-06-07 10:17 180阅读 0赞

# 最大子数组问题 #

从一个数组中寻找一个子数组（最少一个元素），使子数组中元素之和最大（必定包含负数，不然最大子数组就是原数组本身）。

## 暴力求解 ##

我们很容易的想到一个暴力的方法来求解

struct Res{
    
        int low,
        int hi,
        int sum
    
    };
    
    
    
    Res maxSubArray(int *arr ,int len){
    
        int temp=0;
        Res r;
        r.sum=INT_MIN;
        for(int i=0;i<len;i++){
            r.low=i;
            for(int j=i;j<len;j++){
                r.hi=j;
                for(int k=i;k<=j;k++){
                    tmp+=arr[k];            
    
                }
                if(tmp>sum){
                    r.sum=tmp;
    
                }   
    
            }
    
        }
    
        return r;
    
    }

我们很轻松的便知道这个算法的复杂度为O(n3) 空间复杂度为O(1).这个没什么好解释的我们接着看。

**优化版本：**  
我们很容易可以想到，第三层的循环和第二层的循环做了重复的事情，我们来改一改代码

#include<iostream>
    #include<climits>
    struct Res{
    
        int low,
        int hi,
        int sum
    
    };
    
    
    
    Res maxSubArray(int *arr ,int len){
    
        int temp=0;
        Res r;
        r.sum=INT_MIN;
        for(int i=0;i<len;i++){
            r.low=i;
            for(int j=i;j<len;j++){
                r.hi=j;
                tmp+=arr[k];        
                if(tmp>sum){
                    r.sum=tmp;
    
                }   
    
    
            }
    
        }
    
        return r;
    
    }

可以看见复杂度已经降到了O(n2)，然而这并没有什么用。是时候我们要开动脑经了。

## 归并求解 ##

归并的核心思想就是分治法。当一个待处理的问题非常庞大时。我们可以把问题划分为规模较小的原问题来处理，之后合并结果。所以关键就在于规模较小的原问题。

**问题分析**  
对于归并求解最大子数组问题。我们首先想到的是缩小原问题的规模。例如我们用二分归并来划分原问题的数组A\[i\],i>0。分割点在m,0<=m<=i这样原问题就被分为等价的两个小问题。现在我们来考虑最大子数组的存在在哪，可能在A\[0...m\]中可能在A\[m...i\]中，更有可能在A\[k1...k2\],0<=k1<=m<=k2<=i这种，对于前两种情况的求解就又回到了较小规模的原问题上了。所以关键问题的处理就落在了就在分割点上了。一下是代码实现

#include<iostream>
    #include<climits>
    
    using namespace std;
    
    struct Result{
    
        int left_max;
        int right_max;
    
        int sum;
    
    };
    
    
    
    
    
    
    
    Result find_max_crossing_subarray(int * arr,int l, int m ,int r){
    
        int left_sum=0;
        int sum =0; 
        int left_max=INT_MIN;
    
        for(int i=m;i>=l;i--){
    
            sum+=arr[i];
            if(sum>left_sum){
                left_sum=sum;
                left_max=i;
            }
    
    
        }
    
        sum=0;
        int right_sum=0;
        int right_max=INT_MIN;
    
        for(int i=m+1;i<=r;i++){
    
            sum+=arr[i];
            if(sum>right_sum){
    
                right_sum=sum;
                right_max=i;
            }
    
        }
        Result res={left_max,right_max,left_sum+right_sum};
    
        return res;
    
    }
    
    
    Result find_maximum_subarray(int* arr,int l,int r){
    
        if(l==r){
       //不能归并的情况，也就是停止递归的点
             Result res={l,r,arr[l]};
            return res;
        }
        else {
            //同一个问题的较小规模情况
            int m= (l+r)/2  ;
            Result left_r,right_r,cross_r;
            left_r=find_maximum_subarray(arr,l,m);
            right_r=find_maximum_subarray(arr,m+1,r);
    
            cout<<l<<"|"<<m<<"|"<<r<<endl;
    
            //不能归并的情况
            cross_r=find_max_crossing_subarray(arr,l,m,r);
    
            //从上面两种情况下比较结果
            if(left_r.sum>=right_r.sum&&left_r.sum>=cross_r.sum){
    
                return left_r;
    
            }else if(right_r.sum>=left_r.sum&&right_r.sum>=cross_r.sum){
    
    
                return right_r;
            }else{
    
    
                return cross_r;
            }
        }
    
    
    
    
    }
    
    
    
    
    
    int main(){
    
        int arr[16]={
       13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
    
    
        Result r=find_maximum_subarray(arr,0,15);
        cout<<"-----------"<<endl;
        cout<<r.left_max<<"|"<<r.right_max<<"|"<<r.sum<<endl;
    
    
        return 0;
    }

上述归并的时间复杂度为O(nlog2n)空间复杂度为O(n)，如果不了解为什么请自行百度

## 动规求解 ##

动态规划和归并很像。都是同归子问题来推导原问题。但是归并各个子问题是相互独立没有联系的。但是动态规划各层子问题是有联系的，很像数学上面的递推。

**问题分析一**

假如我们知道A\[i...j\]中的最大子数组为maxij。那么A\[i...j\+1\]中的最大子数组在哪呢。可能还是maxij也可能是在A\[m...j\+1\]，i≤m≤j\+1中。这个很关键，如果不懂请自己举例看看，弄懂了再往下看。  
所以问题的关键就是最后一种情况：在A\[m...j\+1\]，i≤m≤j\+1中寻找最最大值。现在我们考虑怎么解决此情况

先跟着意识走，从左向右进行相加。代码如下：

int maxSubArr(int* arr,int low,int hi){
    
        int sum=0;
        int max=INT_MIN;    
    
        if(hi>low){
    
            max=maxSubArr(arr,low,hi-1);
    
            for(int i=low;i<=hi;i++){
                for(int j=i ;j<=hi;j++){
                    sum+=arr[j];
    
                }   
                if(sum>max){
                    max=sum;
    
                }
                sum=0;
            }
    
    
        }else{
            max=arr[low];
        }
    
    
        return max;
    }

可以看见这种方法是非常愚蠢的，中间存在非常多的重复计算，虽然复杂度是O(n2).但实际情况完全不如一开始的暴力枚举。我们的思考方向错了吗。说不定还能抢救一下。现在我们来优化一下上面的代码

int completed[20][20];
    int maxSubArr(int* arr,int low,int hi){
    
        int sum=0;
        int max=INT_MIN;    
    
        if(hi>low){
    
            max=maxSubArr(arr,low,hi-1);
    
            for(int i=low;i<=hi;i++){
    
                if(completed[i][hi-1]!=-1){
                    sum=completed[i][hi-1]+arr[hi]; 
    
                }else{
                    int j;
                    for(j=i ;j<=hi;j++){
                        sum+=arr[j];
    
                    }   
                    completed[j][hi]=sum;
    
                }
    
    
                if(sum>max){
                    max=sum;
    
                }
                sum=0;
            }
    
    
    
        }else{
            max=arr[low];
        }
    
    
        return max;
    }
    
    
    
    int main(){
    
        for(int i=0;i<20;i++)
            for(int j=0;j<20;j++)
                completed[i][j]=-1;
    
        int arr[16]={
       13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
    
        cout<<maxSubArr(arr,0,15)<<endl;
    
        return 0;
    }

我们已经做了很多努力了（空间换时间），让其不重复计算。但是其时间复杂度还是O(n2),可见我们的的思考方向有问题。

现在来看看从右向左的情况：

int maxSubArr(int* arr,int low,int hi){
    
        int sum=0;
        int max=INT_MIN;    
    
        if(hi>low){
    
            max=maxSubArr(arr,low,hi-1);
    
            for(int i=hi ;i>=low;i--){
                sum+=arr[i];
                if(sum>max){
                    max=sum;
                }
            }
    
        }else{
            max=arr[low];
        }
    
    
        return max;
    
    
    
    }

可以发现函数中间的for循环式在做加法，且每一层都是会少一个元素，所以会做(n\+1)n/2次加法。时间复杂度为O(n2)。 o(>﹏<)o不要啊

接着考虑，如果像之前一样预先保存计算的结果来减少计算的重复会怎么样呢？不难发结果还是一样的。上面所有的程序的本质是把数组A\[i\],i>0中的最大子数组枚举一遍。算法的复杂度和暴力枚举是一样的。但是程序额外的开销还有递归造成的庞大堆栈和存值的数组空间。

所以我们思考的方向还是错的。这样的固有思维只会让算法变得更慢，还不如暴力枚举。(╯﹏╰）。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  
**问题分析二**

我们开动脑经。上面解决方案的复杂度最快是O(nlon2n)（归并）。我们必须要找到小于这个复杂度的解决方案，比如O(n).这可是所有算法都想要的完美复杂度了，难度自然不小。对于O(n)的复杂度我们最容易想到的就是用一个for循环来遍历。

我们仔细考虑可以知道最大子数组就是从数组的一边开始加到另一边然后比较这个值是不是最大。因为存在负数所以我们每一次的相加的值可能还没有当前值值大，既然没有当前值大为什么不用这个值当做最大子数组的起始值呢（这句话是这个算法的核心）。如果比当前值大不就是最大子数组的一部分吗。  
公式如下：

sumi,j\+1=\{ A\[j\+1\]sumi,j\]\+A\[j\+1\]sumi,j\+A\[j\+1\]<A\[j\+1\]sumi,j\+A\[j\+1\]≥A\[j\+1\]

如果我们把上面的i带入0，就会的到0到j+1的递推公式

sum0,j\+1=\{ A\[j\+1\]sum0jsum0j\+A\[j\+1\]<A\[j\+1\],sum0j\+A\[j\+1\]≥A\[j\+1\]

这样每一个sum 就存储着到当前值位置的最大子数组中元素和。接着我们找到其中的最大值就可以找到最大子数组了。代码如下

int maxSubArr(int* arr,int low,int hi){
    
        int * sum=new int [hi+1];
        int max=arr[low];
        int tmp;
        sum[low]=arr[low];
        int begin=low;
        int end=hi;
        for(int i=low+1;i<=hi;i++){
            if(sum[i-1]+arr[i]>arr[i]){     
                sum[i]=sum[i-1]+arr[i];
    
            }else{
    
                sum[i]=arr[i];
                begin=i;
            }
    
            if(sum[i]>max){
    
                max=sum[i];
                end=i;
            }else{
    
    
                max=max;
            }
    
    
    
        }
    
        cout<<max<<"|"<<begin<<"|"<<end<<endl;
        return max;
    }

【参考】  
[http://blog.csdn.net/liu2012huan/article/details/51296635][http_blog.csdn.net_liu2012huan_article_details_51296635]

[http_blog.csdn.net_liu2012huan_article_details_51296635]: http://blog.csdn.net/liu2012huan/article/details/51296635