数组的子数组之和的最大值

        求子数组之和的最大值是一个很经典的问题。问题的描述如下：一个有N个整形数的一维数组（A[0], A[1], ... A[n-1]），这个数组有很多子数组，那么子数组之和的最大值是什么呢？

         这个问题的解答其实在《编程珠玑》一书有的。一共是4中方法：第一种是穷举法，计算所有可能子数组的和，时间复杂度为O(n3)。

 

第二种其实也是穷举法。代码如下：

[cpp] view plaincopy

 

         很明显复杂度为O(n2)。第三种方法是分治法，将数组元素均分成两部分，那么最大子数组和只有三种情况。在左边部分，右边部分，以及跨越了边界部分。这种方法是时间复杂度为O(nlogn)。不是最优的就不列代码了。

第四种是最优的，时间复杂度为O(n)，利用了动态规划的思想。具体代码如下：

 

A[0]是首元素，

start[1]是包含a[1]的和最大的数组，

all[1]是可能包含也可能不包含a[1]的和最大的数组，

所以a[0]…..a[n-1]的解all[0]是max｛a[0],   a[0]+start[1],  all[1]｝;

 

这个代码有额外申请了两个数组，下面是改进的算法，避免开辟数组空间

 

 

分治算法的模型

 

[cpp] view plaincopy

还可以进行下一步的改进;

} 
 

        这种方法不论是空间和时间都已是最优的了，在《编程之美》中列举了改进的过程，最终的程序就是上面的这段代码。

        如果是二维数组呢，又当如何解答。《编程之美》中给出的解法是穷举矩形区域的所有可能的上下边界，再用一维的方法计算该上下边界的最大和。时间复杂度为 O(n2*m)。当然也可以先穷举矩形区域的所有可能的左右边界。本质上是一样的。下面给出了一种解法。这里用了一个辅助数组B，B[ i ][ j ]表示第 j 列元素的前 i  行元素的和。B[ i + 1 ][ j ]=A[ 0 ][ j ]+A[ 1 ][ j ]+...A[ i ][ j ]。B[ 0 ][ j ]做为哨兵，全部为0。

[cpp] view plaincopy

问题描述：

一个有N个整数元素的一维数组(A[0],A[1],...A(n-1),它包含很多子数组，求子数组之和的最大值，当数组元素全部为负的时候，有两种处理办法，第一种是返回0，第二种是返回数组中最大的负数。

解法1：

使用暴力法，假设最大的一段数组为A[i],...,A[j]，则对i:=0~n-1 j:=i~n-1，遍历一遍，求出最大的Sum(i,j)即可

解法2：

使用分治法，数组(A[0],A[1],...A(n-1)分为长度相等的两段数组(A[0],...,A[n/2])以及(A[n/2+1],...,A[n-1])，分别求出这两段数组各自的最大子段和，则原数组(A[0],A[1],...A(n-1)的最大子段和分为3种情况
1)(A[0],A[1],...A(n-1)的最大子段和与(A[0],...,A[n/2])的相同
2)(A[0],A[1],...A(n-1)的最大子段和与(A[n/2+1],...,A[n-1])的相同
3)(A[0],A[1],...A(n-1)的最大子段和跨过(A[0],...,A[n/2])与(A[n/2+1],...,A[n-1])

解法3：
使用动态规划法，假设A[0],A[1],...A(n-1)的最大子段为A[i],...,A[j]，则有以下3种情况
1)当0=i=j的时候，元素A[0]本身构成和最大的一段
2)当0=i<j的时候，和最大的一段以A[0]开头
3)当0<i时候，元素A[0]跟和最大的一段没有关系
则原始问题A[0],A[1],...A(n-1)的解All[0]=max{A[0],A[0]+Start[1],ALL[1]}

 

程序说明：

下面的程序中，针对数组全部为负的情况的处理（处理1：直接返回0，处理2：返回数组中最大的负数）定义了两种情况，分别对应于定义了RETURN_ZERO和RETURN_MAXMINUS这两种情况

 

    /*********************问题描述******************

一个有N个整数元素的一维数组(A[0],A[1],...A(n-1),
    它包含很多子数组，求子数组之和的最大值，当数组元
    素全部为负的时候，有两种处理办法，第一种是返回0，
    第二种是返回数组中最大的负数
    ************************************************/  
    #include<iostream>  
    using namespace std;  
      
      
    //定义了RETURN_ZERO说明处理全部为负数的数组时候返回0  
    #define RETURN_ZERO  
    #ifdef RETURN_ZERO  
    /*******************************解法一：蛮力法*****************************
    依次计算A[0],A[0..1],...A[0..n-1],A[1],A[1..2]...A[1..n-1],A[2],A[2..3],...
    A[2..n-1]...并返回最大的值maximum
    ****************************************************************************/  
    int MaxSum1(int *A,int length){  
        int maximum=0;          //子数组和最大值  
        int sum;                //子数组和  
        for(int i=0;i<length;i++){  
            sum=0;  
            for(int j=i;j<length;j++){  
                sum+=A[j];  
                if(sum>maximum)  
                    maximum=sum;  
            }  
        }  
        return maximum;  
    }  
    /*******************************解法二：分治法*******************************
    数组(A[0],A[1],...A(n-1)分为长度相等的两段数组(A[0],...,A[n/2])以及(A[n/2+1],
    ...,A[n-1])，分别求出这两段数组各自的最大子段和，则原数组(A[0],A[1],...A(n-1)
    的最大子段和分为3种情况：
    1)(A[0],A[1],...A(n-1)的最大子段和与(A[0],...,A[n/2])的相同
    2)(A[0],A[1],...A(n-1)的最大子段和与(A[n/2+1],...,A[n-1])的相同
    3)(A[0],A[1],...A(n-1)的最大子段和跨过(A[0],...,A[n/2])与(A[n/2+1],...,A[n-1])
    *****************************************************************************/  
    int MaxSum2(int *A,int left,int right){  
        if(left==right){  
            return max(A[left],0);  
        }  
        int middle=(left+right)/2;  
        //求(A[0],...A[n/2-1])中子数组包含A[n/2-1]的最大值  
        int lmaximum=0;  
        int lsum=0;  
        for(int i=middle;i>=left;i--){  
            lsum+=A[i];  
            if(lsum>lmaximum)  
                lmaximum=lsum;  
        }  
        //求(A[n/2],...,A[n-1])中子数组包含A[n/2]的最大值  
        int rmaximum=0;  
        int rsum=0;  
        for(int i=middle+1;i<=right;i++){  
            rsum+=A[i];  
            if(rsum>rmaximum)  
                rmaximum=rsum;  
        }  
        return max(lmaximum+rmaximum,max(MaxSum2(A,left,middle),MaxSum2(A,middle+1,right)));  
    }  
    /******************************解法三：动态规划**********************************
    假设A[0],A[1],...A(n-1)的最大子段为A[i],...,A[j]，则有以下3种情况，
    1)当0=i=j的时候，元素A[0]本身构成和最大的一段
    2)当0=i<j的时候，和最大的一段以A[0]开头
    3)当0<i时候，元素A[0]跟和最大的一段没有关系
    则原始问题A[0],A[1],...A(n-1)的解All[0]=max{A[0],A[0]+Start[1],ALL[1]}
    *********************************************************************************/  
    //从尾到首动态规划（编程之美2.14的思想）  
    int MaxSum3(int *A,int length){  
        int nStart=0;  
        int nAll=0;  
        for(int i=length-1;i>=0;i--){  
            nStart=max(0,A[i]+nStart);  
            nAll=max(nStart,nAll);  
        }  
        return nAll;  
    }  
    //从首到尾动态规划（编程珠玑8.4思想）  
    int MaxSum3_v2(int *A,int length){  
        int nStart=0;  
        int nAll=0;  
        for(int i=0;i<length;i++){  
            nStart=max(0,A[i]+nStart);  
            nAll=max(nStart,nAll);  
        }  
        return nAll;  
    }  
    #endif 

 

 

这个问题源于《编程之美》2.14 求数组的子数组之和的最大值扩展问题2

输出子数组的最大和同时输出子数组下标，时间复杂度为O(N)
源码：

#include <iostream>
using namespace  std;
//startPos 最大和子数组的起始位置 
//endPos 最大和子数组的结束位置  
int MaxSum(int *A,int n,int &startPos,int &endPos)
{
    int tmpStart = 0;
    int nStart = A[0];
    int nAll = A[0];
    for (int i=1;i<n;i++)
     {
        if(nStart < 0)
         {
            nStart =0;
            startPos = i;
        }
        nStart += A[i];
        if (nStart>nAll)
         {
            nAll = nStart;
            endPos =i;
            tmpStart = startPos;
        }
    }
    startPos = tmpStart;
    return nAll;
}
int main()
{
    int arr[11] =  {-2,5,6,-6,4,-8,6,3,-1,2,-9};
    int startP = 0,endP = 0;
    int maxsubArrSumValue =0;
    maxsubArrSumValue = MaxSum(arr,11,startP,endP);
    cout<<maxsubArrSumValue<<endl<<startP+1<<endl<<endP+1<<endl;

    system("pause");
    return 0;
}

 

 

二维的情况

最直接的方法就是枚举

int max(int x,int y)

{

return (x>y) ? x:y;

}

 

int MaxSum(int * A,int n,int m)

{

maxinum=-INF;

for(i_min=1;i_min<=n;i_min++)

    for(i_max=i_min;i_max<=n;i_max++)

         for(j_min;j_min<=m;j_min++)

              for(j_max=j_min;j_max<=m;j_max++)

             maximum=max(maximum,Sum(A,i_min,i_max,j_min,j_max));

return maximum;

}

 二维中，假设已经确定了矩形区域的上下边界，比如知道矩形区域的上下边界分别是第a行和第c行，现在要确定左右边界。 
 
转化为一个一维问题，可以把每一列中第a行和第c行之间的元素看成一个整体。即求数组(BC[1],...BC[M])中和最大的一段，其中B[i] = B[a][i]+...B[c][i]. 

为了优化程序，我们可以先做一些预处理，并把计算结果保留下来

定义PS[i][j] 为以(1,1),(i,1),(1,j),(i,j)为边界的矩形区域元素之和

所以任意区域之和可以表示成

PS[i_max][j_max]-PS[i_min-1][j_max]-PS[i_max][j_min-1]+PS[i_min-1][j_min-1];

for(int i=0;i<=n;i++)

PS[i][0]=0;

for(int j=0;j<=M;j++)

PS[0][j]=0;

for(int i=1;i<=n;i++)

      for(int j=1;j<=M;j++)

           PS[i][j]=PS[i-1][j]+PS[i][j-1]+PS[i-1][j]-PS[i-1][j-1]+B[i][j];

 

另外的一种解法就是将二维的问题转换为一维的问题：

假设我们已经确定了矩形的上下边界分别是a，c那么现在需要确定左右边界，问题转换成求一维情况下的最大和

int MaxSum(int * A,int n,int m)

{

maximum=-INF;

for(int a=1;a<=n;a++)

     for(int c=a;c<=n;c++)

     {

         Start=BC(a,c,m);

         ALL=BC(a,c,m);

         for(int i=m-1;i>=2;i--)

             {

              if(Start<0)

              Start=0;

              Start+=BC(a,c,i);

              if(Start > ALL)

              All=Start;

             }

              if(All > maximum)

               maximum=ALL;

     }

return maximum;

}