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[100][100],k,t,c,i,j,z;
    int maxsum,sum[100],max=0;
    cout<<"请输入矩阵的行数和列数:"<<endl;
    cin>>m>>n;
    srand((unsigned)time(NULL));
    for(i=0;i<m;i++)
     {
         for(j=0;j<n;j++)
         {
             a[i][j] = rand() %140 - 70;
             cout<<a[i][j]<< " ";
         }
         cout<<endl;
     }
        for(k=0;k<m;k++)
        {
            //初始化一个m*n型的二维数组,以作为储备每一个细化的子矩阵之和
            for(c=0;c<n;c++)
            {sum[c]=0;}
            //求此矩阵划分而得的每一个子矩阵之和
            for(j=k;j<n;j++)
            {
                for(i=0;i<m;i++)
                {
                    sum[i]+=a[i][j];
                }
                //依次比较所得到的每个子矩阵之和取最大子矩阵之和
                   for(t=0;t<m;t++)
                   {
                    maxsum=0;
                    for(z=t;z<n;z++)
                    {
                        maxsum+=sum[z];
                        if(maxsum>max)
                            max=maxsum;
                    }
                   }
            }
        }
       cout<<"最大子矩阵之和为:"<<max;

}

3.实验截图:

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

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

时间: 04-07

Task 4.2 求一个矩阵的最大子矩阵的和的相关文章

求一个矩阵中最大的2*2矩阵(元素和最大)的和

编程题在线编程题30分2/2最大子矩阵Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Problem Description:求一个矩阵中最大的2*2矩阵(元素和最大)的和.如:1 2 0 3 42 3 4 5 11 1 5 3 0中最大的是:4 55 3和为17输入m*n的矩阵输出该m*n矩阵的最大2*2子矩阵(元素和最大)的和 样例输入 1 2 0 3 4 ; 2 3 4 5 1 

【编程题目】求一个矩阵中最大的二维矩阵(元素和最大)

35.(矩阵)求一个矩阵中最大的二维矩阵(元素和最大).如:1 2 0 3 42 3 4 5 11 1 5 3 0中最大的是:4 55 3要求:(1)写出算法;(2)分析时间复杂度;(3)用 C 写出关键代码 早上灭小题! /* 35.(矩阵) 求一个矩阵中最大的二维矩阵(元素和最大).如: 1 2 0 3 4 2 3 4 5 1 1 1 5 3 0 中最大的是: 4 5 5 3 要求:(1)写出算法;(2)分析时间复杂度;(3)用 C 写出关键代码 */ #include <stdio.h>

hdu 1575 求一个矩阵的k次幂 再求迹 (矩阵快速幂模板题)

Problem DescriptionA为一个方阵,则Tr A表示A的迹(就是主对角线上各项的和),现要求Tr(A^k)%9973. Input数据的第一行是一个T,表示有T组数据.每组数据的第一行有n(2 <= n <= 10)和k(2 <= k < 10^9)两个数据.接下来有n行,每行有n个数据,每个数据的范围是[0,9],表示方阵A的内容. Output对应每组数据,输出Tr(A^k)%9973. Sample Input22 21 00 13 999999991 2 34

求一个矩阵的逆矩阵(用伴随矩阵求)

题目:noyj774 用代数余子式求逆矩阵方法: 若现有矩阵A,要求其逆矩阵: 若|A|==0,则其不存在逆矩阵: 若|A|!=0,其逆矩阵A^-1==*A/|A|:其中*A为其伴随矩阵: 伴随矩阵的求法: *A[j][i]==|M[i][j]|,其中M[i][j]为A[i][j]的代数余子式: 即*A1[i][j]==|M[i][j]|,再将*A1转置得到*A: 代码: #include<bits/stdc++.h>#define MAXN 10#define MAX 100000000#d

睡觉前请关灯的 破解尝试版本 由已知解求一个矩阵的步骤

#include<iostream> #include"wz.h" #include<ctime> using namespace std; #define  MAX  5 void show(int arr[][MAX]) {  for(int i=0;i<MAX;i++)  {   for(int j=0;j<MAX;j++)   {    cout<<arr[i][j]<< " ";   }   co

一个矩阵的所有子矩阵最大和问题

Preface ??今天早上刷微博,看到LeetCode中国微博发了这样一条状态: ??已经好久没做题练练手了,于是想试试.LeetCode上,该题目的地址为:https://leetcode.com/problems/max-sum-of-sub-matrix-no-larger-than-k/ Analysis ??想了一上午,也没想出什么头绪.后来我看 LeetCode 上有不少人已经做出提交了.并且,在discuss页面里,有人公布了详细的解释与代码. ??我看了一下,他这个解法是基于K

IT公司100题-35- 求一个矩阵中最大的二维矩阵(元素和最大)

问题描述: 求一个矩阵中最大的二维矩阵(元素和最大).如: 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 中最大的是: 4 5 9 10 分析: 2*2子数组的最大和.遍历求和,时间复杂度为O(mn). 代码实现: 1 // 35.cc 2 #include <iostream> 3 #include <climits> 4 using namespace std; 5 6 int find_max(int (*a)[5], int m, int n) { 7 in

matlab中如何求某一个矩阵的标准差和均值

方法: 先reshape成行向量或者列向量 然后,利用mean函数,std函数. 构造测试数据,可以利用random函数,就好.利用这个函数,可以构造不同分布的随机数列(或 矩阵). 如: >> y =random('norm',2,0.3,3,4) y = 2.1391 2.2945 2.0769 2.1751 1.9334 1.6805 1.9315 1.8912 1.8775 1.8126 1.9733 1.7686 >> rows = reshape(y,3*4,1) ro

用递归实现求一个迷宫是否有通路

今天终于把昨天下午没写出来的迷宫求是否有通路的cpp写出来了 使用递归实现的,不过算法的质量不怎么样,使用穷举法实现的. 在网上搜了一下,发现还有很多的更优的算法,哈哈,不过怎么说都是自己一个个地代码敲出来的. 特点是发现在linux下面调试真的有时候自己会崩溃,还好最终还是搞出来了. 哈哈,发上来给类似我这种的算法新手来一起分享一下: 路径就记录在栈里面,需要得出具体路径的可以小改一下就行了. findRoad.cpp //迷宫求解问题思路 //1.用一个矩阵来表示迷宫,即n*m数组 //用穷