求二维数组最大子数组的和。郭林林&胡潇丹

时间：2021-10-06 15:42:09

求二维数组子数组的最大值，开始思路不太清晰。先从最简单的开始。

以2*2的简单数组为例找规律，

假设最大数为a[0][0],则summax=a[0][0]，比较a[0][0]+a[0][1]、a[0][0]+a[1][0]、a[0][0]+a[0][1]+a[1][0],最后求出summax;

3*3 的数组同理：

假设最大值为a[0][0],则summax=a[0][0]，比较a[0][0]所在行和列的最大子数组，取大的赋值给summax，接着扩充数组，继续比较，求出summax；

m*n 的数组即为：

先求出数组中的最大值a[i][j]，将它赋值给summax(最大子数组之和)；

然后在a[i][j]所在行上，进行扩展，找到行上的最大行的连续数组；

同理，在所在列上继续寻找，找到列上的最大连续数组；

然后以找到的行列数组为框架，继续寻找更大的子数组；

依次比较，最终求出最大子数组的和。

程序实现：

 //求二维数组的连续子数组之和的最大值

 int MaxSum(int (*array)[N])

 {

     int PartSum[N+][M+];

     int i,j;

     for(i=;i<=N;i++)

         PartSum[i][]=;

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

         PartSum[][j]=;

     for(i=;i<=N;i++)

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

             PartSum[i][j]=PartSum[i-][j]+PartSum[i][j-]-PartSum[i-][j-]+array[i-][j-];

     int MaxSum=-INFINITY;//初始化

     int imin,imax,jmin,jmax;

     for(imin=;imin<=N;imin++)

         for(imax=imin;imax<=N;imax++)

             for(jmin=;jmin<=M;jmin++)

                 for(jmax=jmin;jmax<=M;jmax++)

                         MaxSum=MaxNum(MaxSum,PartSum[imax][jmax]-PartSum[imin-][jmax]-PartSum[imax][jmin-]+PartSum[imin-][jmin-]);

     return MaxSum;

 }

 #include<iostream>

 using namespace std;

 int maxSum(int *a, int hang, int lie)

 {

     int sum=;

     for(int i=;i<hang;i++)

     {

         for(int j=;j<lie;j++)

         {

             for(int k=i;k<hang;k++)

             {

                 for(int l=j;l<lie;l++)

                 {

                     sum = ;

                     for(int n=i; n<=k;tn++)

                         for(int m=j; m<=l;m++)

                         {

                             sum += a[n*lie+m];                        }

                      b= max(sum,b);

                 }

             }

         }

     }

      cout<<"最大的子数组和:"<<b<<endl;

 }

 int main()

 　{

 　　int a[][]={{,-,，}，{，,，-}，{,，,}，{,-，，}};

     maxSum( a, ,);

   }

相关文章