Task 4.2 求一个矩阵的最大子矩阵的和

任务:输入一个二维整形数组，数组里有正数也有负数。二维数组中连续的一个子矩阵组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。

(1)设计思想：把二维矩阵分解成行、列的情况，可以相应把问题简化。之后分别依照行和列的基准来求每一个矩阵的和，再依次进行比较每个矩阵的和。最容易想到也是最容易实现的方法。遍历矩阵(行迭代器为i,列迭代器为j)，以当前遍历到的元素为首a[i,j]，计算二维子矩阵的和(sum=a[i,j]+a[i+1,j]+a[i,j+1]+a[i+1,j+1])，并找出和最大的二维矩阵，注意矩阵的最后一行和最后一列不用遍历。时间复杂度为O(i*j)。

改进方法如下：

a.原先每次访问四个元素，现在变为每次访问纵向的两个元素（a[i,j],a[i+1,j]），横向遍历，遍历的起始点改为第二个元素，终点到最后一个元素。

b.改变求和方式，求和方法是：首先将上一次保存的和last_vsum加进sum中，再将last_vsum更新为当前纵向的两个元素a[i,j],a[i+1,j]之和，然后再将last_vsum加入sum中，这样就得到本次二维矩阵的和可与maxsum进行比较。如此每次求和只需访问两个元素a[i,j],a[i+1,j]。

(2)代码：

#include<iostream>

#include<time.h>

using namespace std;

void main()

{

    int m,n,a[][],k,t,c,i,j,z;

    int maxsum,sum[],max=;

    cout<<"请输入矩阵的行数和列数："<<endl;

    cin>>m>>n;

    srand((unsigned)time(NULL));

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

     {

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

         {

             a[i][j] = rand() % - ;

             cout<<a[i][j]<< " ";

         }

         cout<<endl;

     }

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

        {

            //初始化一个m*n型的二维数组，以作为储备每一个细化的子矩阵之和

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

            {sum[c]=;}

            //求此矩阵划分而得的每一个子矩阵之和

            for(j=k;j<n;j++)

            {

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

                {

                    sum[i]+=a[i][j];

                }

                //依次比较所得到的每个子矩阵之和取最大子矩阵之和

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

                   {

                    maxsum=;

                    for(z=t;z<n;z++)

                    {

                        maxsum+=sum[z];

                        if(maxsum>max)

                            max=maxsum;

                    }

                   }

            }

        }

       cout<<"最大子矩阵之和为："<<max;

}

3.实验截图：

4.总结：（1）开始上课的时候就在找各种方法实现，比如找到矩阵中的最大和再扩展开求最大矩阵和；或是找出所有正数根据正数的个数和大小判断求出最大矩阵和；但是最终都没有得出一个完整的思路，因为都太难实现了而且总会有一些细节与期望值不相符。所以最后我们两个就重整思路写出了这个程序。

（2）要学会把一个复杂的项目分解，因为只有学会了分解以后才能更快更好地解决所有的问题。

巴特西

Task 4.2 求一个矩阵的最大子矩阵的和

最新文章

热门文章