数据结构算法题/最大子矩阵(二维数组中和最大的连续子矩阵)_二维数组最大子序列矩阵题目-程序员宅基地

技术标签: 算法导论  

给定一个矩阵,都是整数,求出其中的最大子矩阵。

可以将问题转换为求一维数组的最大子序列和的问题。具体见https://blog.csdn.net/fkyyly/article/details/83088247

/**
 * 其实思想是控制新的子矩阵开始,按列相加变成一维数组,然后再求一维数组最大子序列的和,
 * 最后在多个最大子序列的和中返回最大的那个
 * 然后对如上获取的不同子矩阵分别按列相加生成很多的一维数组
 * 然后对每个数组分别求最大子数组的和(因为是求最大子数组的和,所以只需要控制开始的行,不需要控制结束的行也不需要控制开始和结束的列)
 * 因为求最大子数组的和可以是中间几个元素的和
 * 然后从所有子数组对应的最大子数组的和中选出最大的值
 *
 * 个人认为如果是限制行的开始,那么就按列相加,然后对一维数组求最大子数组的和
 * 如果是限制列的开始,那么就按行相加,然后对一维数组求最大子数组的和
 */
public class MaxSumofMatrix {
    public static void main(String[] args) {
        //最大子矩阵的累加和
        int matrix[][]={
   {-1,-1,-1},{1,2,2},{8,-7,-1},{-1,100,-1}};
        maxMatrixSum(matrix);
    }

    public static void maxMatrixSum(int matrix[][])
    {
        if(matrix==null||matrix.length==0)
            return;
        int max=0;
        int col=matrix[0].length,row=matrix.length;
        for(int i=0;i<col;i++)
        {
            int arr[]=new int[col];//存储对应列的和,按列相加

            //表示子矩阵从i行开始
            for(int j=i;j<row;j++)
            {
                //下面的循环结合上面的循环就是按列相加
                //所以有多少列,arr就有多少个数
                for(int k=0;k<col;k++)
                {
                    arr[k]+=matrix[j][k];
                    // 如果子矩阵是从0开始的话也就是j=i=0,arr[0]=matrix[0][0]+matrix[1][0]+matrix[2][0]+matrix[3][0]+...(所有行的第0个元素)
                    // 如果子矩阵是从1开始的话也就是j=i=1,arr[0]=matrix[1][0]+matrix[2][0]+matrix[3][0]+...(去除第0行的第0个元素)
                    // 如果子矩阵是从1开始的话也就是j=i=10,arr[0]=matrix[10][0](去除前9行的第0个元素)
                    // 比较上面三个表达式,行数在减少
                    // 将每子行的值进行相加然后利用子数组的最大和就可以求出子矩阵的最大和
                }
                max=Math.max(maxArrSum(arr), max);
                //求出数组的子数组和最大值
            }
        }
        System.out.println(max);
    }


    public static int maxArrSum(int arr[])
    {
        int max=0,sum=0;
        for(int i=0;i<arr.length;i++)
        {
            if(sum<=0)
            {
                sum=arr[i];
            }
            else {
                sum+=arr[i];
            }
            max=Math.max(sum, max);
        }
        return max;
    }
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/fkyyly/article/details/84111268

智能推荐

简单几步,让微信小程序变身 H5 网页_小程序转换成网页 在线-程序员宅基地

文章浏览阅读4.9k次。云开发(Tencent Cloud Base,TCB)是腾讯云为移动开发者提供的一站式后端云服务,它帮助开发者统一构建和管理资源,免去了移动应用开发过程中繁琐的服务器搭建及运维、域名注册及备案、数据接口实现等繁琐流程,让开发者可以专注于业务逻辑的实现,而无需理解后端逻辑及服务器运维知识,开发门槛更低,效率更高。官方教程:https://tencentcloudbase.github.io/We..._小程序转换成网页 在线

TMainMenu 类 - 手动建立菜单 : 指定快捷键《转》-程序员宅基地

文章浏览阅读87次。菜单项通过 ShortCut 属性来设定快捷键, ShortCut 是 TShortcut 类型的; TShortcut 是一个子界: 0..65535ShortCut 的所有可选值请参加列表:http://www.cnblogs.com/LceMeaning/archive/2013/01/09/2853071.html================================..._tmenuitem.shortcut

slidebox使用教程 设定焦点数量-程序员宅基地

文章浏览阅读1.1k次。如下图所示的class="num" 下的a标签有几个就有几个焦点,对应下面的<li>标签的图片,js设定图片时间<div class="hot left" id="hot"> <div class="num"> <a class="curr"></a> <a></a> <a>&l..._slidebox使用教程

Java基础语法<七> 对象与类 封装-程序员宅基地

文章浏览阅读68次。笔记整理 来源于《Java核心技术卷 I 》 《Java编程思想》1. 类之间的关系1.1 依赖 users– a  是一种最明显的、最常见的关系。如果一个类的方法操作另一个类的对象,我们就说一个类依赖于另一个类。尽可能地将相互依赖的类减至最少。如果类A不知道B的存在,它就不会关心B的任何改变(这意味着B的改变不会导致A产生任何bug)。让类之间的耦合度最小。1.2 聚合 has – ...

关于解决Win7 FTP访问出错解决方案_ftp网页某些内容或文件所需的程序尚未安装-程序员宅基地

文章浏览阅读2.1k次。关于解决Win7 FTP访问出错解决方案遇到的问题:通过资源管理器访问外网FTP出错问题。如下 解决方案:1、打开ie浏览器,选择工具 2、选择Internet选项 3、选择高级 4、去掉”使用被动FTP(用于…)”的勾选 5、通过以上的操作就可以,正常的访问外网FTP服务器了。小小创作,如有任何疑问和错误请指出,谢谢。 创作人:PoorGuy..._ftp网页某些内容或文件所需的程序尚未安装

python api调用百度ai平台_百度ai开放平台使用方法(附带详细案例步骤)-程序员宅基地

文章浏览阅读1.2k次。百度ai开放平台1.百度ai开放平台内有众多功能,如文字识别,语音技术等等内容,本文章以身份证识别为例子,教大家怎么使用它啦链接走起:https://cloud.baidu.com/?from=console身份证识别1.点开链接,即可看到文字识别内的身份证识别,请求说明部分,可以看到bash,python,java,c++,PHP等,这里的例子用的是python,选择python拷贝到代码软件内..._将ai平台导入python

随便推点

使用JAVA实现TCP数据转发-程序员宅基地

文章浏览阅读3.3k次。2019独角兽企业重金招聘Python工程师标准>>> ..._java实现tcp转发nt

轨迹分析—Matlab计算均方位移_matlab知道运动方程求位移-程序员宅基地

文章浏览阅读4k次,点赞2次,收藏13次。热力学性质的不均匀性导致的热力学过程叫做输运过程,相应的现象叫做输运现象。由于粒子数密度的不均匀性导致粒子的输运(扩散现象).由于粒子数密度的不均匀性导致粒子的输运(扩散现象).均方根位移是随时间测量的,以确定粒子是否仅由于扩散而扩散。均方根位移是随时间测量的,以确定粒子是否仅由于扩散而扩散。那么如何根据轨迹文件计算MSD呢?那么如何根据轨迹文件计算MSD呢?_matlab知道运动方程求位移

sama5d2 开发板 使用(一)_setenv bootargs "console=ttys0,115200 mtdparts=atm-程序员宅基地

文章浏览阅读1.9k次,点赞2次,收藏3次。图片: 方便查看,不用一次一次的去看手册设置uboot 参数: 从nandflash 启动:=&gt;setenv bootargs console=ttyS0,115200 earlyprintk mtdparts=atmel_nand:256k(bootstrap)ro,512k(uboot)ro,256K(env),256k(env_redundent),256k(spare..._setenv bootargs "console=ttys0,115200 mtdparts=atmel_nand:256k(bootstrap)ro,

eCognition 面向对象图像分类【分类算法介绍】Classification Algorithms_ecognition随机森林 depth-程序员宅基地

文章浏览阅读4.2k次,点赞2次,收藏19次。目录基本分类算法The Assign Class Algorithm【指向分类算法】基本描述适用范围The Classification Algorithm【特征分类算法】基本描述适用范围The Hierarchical Classification Algorithm【层次分类算法】基本描述适用范围高级分类算法基本分类算法Th..._ecognition随机森林 depth

【前端基础小案例】HTML+CSS打造精美选项卡菜单效果_前端好看的选项卡-程序员宅基地

文章浏览阅读2.3k次,点赞26次,收藏38次。手把手教你打造精美选项卡_前端好看的选项卡

三种登录Jetson Nano的方法_jetson nano usb连接电脑登录-程序员宅基地

文章浏览阅读3.2k次,点赞6次,收藏26次。本文主要介绍三种登录Jetson Nano的方法,大家根据自己需求进行配置。一、直接连接所谓直接连接,就是将Jetson Nano当做主机,使用HDMI连接显示器,通过usb连接键盘和鼠标,然后便像操作电脑一样直接使用。二、使用xshell远程登录先在自己的PC上安装Xshell软件,破解版的百度一搜索就有,下载和安装过程比较简单,不再赘述。由于条件限制,没有路由器,又没有买无线wifi模块,所以我的Jetson Nano是使用网线跟笔记本连接进行上网的,笔记本则是连接手机热点。如果_jetson nano usb连接电脑登录