【算法设计】最大子矩阵问题 - 小田的专栏 - 博客园
一，最大子矩阵问题：
& & & &给定一个n*n(0&n&=100)的矩阵，请找到此矩阵的一个子矩阵，并且此子矩阵的各个元素的和最大，输出这个最大的值。
&0 -2 -7 &0&
&9 &2 -6 &2&
-4 &1 -4 &1&
-1 &8 &0 -2&
其中左上角的子矩阵：
此子矩阵的值为9+2+(-4)+1+(-1)+8=15。
二，分析& & & &
子矩阵是在选取部份行、列所组成的新矩阵。
它亦可用A(3;2)表示，显示除掉第3行和第2列的余下的矩阵。这两种方法比较常用，但还是没有标准的方法表示子矩阵。
以上为维基百科上给出的定义，感觉跟此题的定义不是一回事呢？
& & & & 我们首先想到的方法就是穷举一个矩阵的所有子矩阵，然而一个n*n的矩阵的子矩阵的个数当n比较大时时一个很大的数字 O(n^2*n^2)，显然此方法不可行。怎么使得问题的复杂度降低呢？对了，相信大家应该知道了，用动态规划。对于此题，怎么使用动态规划呢？
& & & & 请先参考--&
& & & & 这个问题与最大子段有什么联系呢？
&假设最大子矩阵的结果为从第r行到k行、从第i列到j列的子矩阵，如下所示(ari表示a[r][i],假设数组下标从1开始)：
& | a11 …… a1i ……a1j ……a1n |
& | a21 …… a2i ……a2j ……a2n |
& | &. & & . & & . & &. & &. & & . & &. & & & & &|
& | &. & & . & & . & &. & &. & & . & &. & & & & &|
& | ar1 …… ari ……arj ……arn & &|
& | &. & & . & & . & &. & &. & & . & &. & & & & &|
& | &. & & . & & . & &. & &. & & . & &. & & & & &|
& | ak1 …… aki ……akj ……akn &|
& | &. & & . & & . & &. & &. & & . & &. & & & & &|
& | an1 …… ani ……anj ……ann |
&那么我们将从第r行到第k行的每一行中相同列的加起来，可以得到一个一维数组如下：
&(ar1+……+ak1, ar2+……+ak2, ……,arn+……+akn)
&由此我们可以看出最后所求的就是此一维数组的最大子段和问题，到此我们已经将问题转化为上面的已经解决了的问题了。
C++:
#include &iostream&
int maxSubArray(int a[],int n)
int b=0,sum=a[0];
for(int i=0;i&n;i++)
int maxSubMatrix(int array[][3],int n)
int i,j,k,max=0,sum=-;
for(i=0;i&n;i++)
for(k=0;k&n;k++)//初始化b[]
for(j=i;j&n;j++)//把第i行到第j行相加,对每一次相加求出最大值
for(k=0;k&n;k++)
b[k]+=array[j][k];
max=maxSubArray(b,k);
if(max&sum)
int main()
int array[3][3]={{1,2,3},{-1,-2,-3},{4,5,6}};
cout&&&MaxSum: &&&maxSubMatrix(array,n)&&
import java.util.S
public class PKU_1050
private int maxSubArray(int n,int a[])
int b=0,sum=-;
for(int i=0;i&n;i++)
private int maxSubMatrix(int n,int[][] array)
int i,j,k,max=0,sum=-;
int b[]=new int[101];
for(i=0;i&n;i++)
for(k=0;k&n;k++)//初始化b[]
for(j=i;j&n;j++)//把第i行到第j行相加,对每一次相加求出最大值
for(k=0;k&n;k++)
b[k]+=array[j][k];
max=maxSubArray(k,b);
if(max&sum)
public static void main(String args[])
PKU_1050 p=new PKU_1050();
Scanner cin=new Scanner(System.in);
int[][] array=new int[101][101];
while(cin.hasNext())
n=cin.nextInt();
for(int i=0;i&n;i++)
for(int j=0;j&n;j++)
array[i][j]=cin.nextInt();
System.out.println(p.maxSubMatrix(n,array));一个关于矩阵的问题？ - 知乎2被浏览96分享邀请回答1添加评论分享收藏感谢收起关于常见矩阵路径计算问题(iOS版本) - 简书
关于常见矩阵路径计算问题(iOS版本)
关于常见矩阵路径计算问题(iOS版本)
729dcafcfcf04f668c94a4c27c1e25e2.jpg
常见类型介绍：
/*●问题描述：
给出一个矩阵，其中0表示通路，1表示墙壁，这样就形成了一个迷宫，要求编写算法求出其中一条路径。
●递归思路：
编写一个走迷宫函数，传入二位数组的下标，先假设该点位于最终路径上（将0置为2）再探测周围四个点是否可以走通（是否为０），如果可以走通则将该点四周能走通的点作为函数参数传入函数进入递归。若四周均不能走通（都不为０时）则将该点置回０表示该点不是最终路径上的点。
　　在此思路中递归进入时表示了枚举路径，当发现此条路径走到某处再不能走通时就将路径该点置回０并且递归退出（回溯）寻找下一条可走通路径。
规则中可以上下左右方向前进，求左上角到右下角的最小步数：
核心在于递归回溯判断，下面贴出代码
int mazeChat(int maze[][5],int i,int j){
int end = 0;
maze[i][j] = 2;
//如果到终点直接置为1
if (i == END_I && j == END_J) {
//不是终点则按照右下左上判断
if (end !=1 && j+1&=END_J && maze[i][j+1] == 0) {
if (mazeChat(maze, i, j+1) == 1) {
if (end !=1 && i+1&=END_I && maze[i+1][j] == 0) {
if (mazeChat(maze, i+1, j)==1) {
if (end !=1 && j-1&=START_J && maze[i][j-1] == 0) {
if (mazeChat(maze, i, j-1) == 1) {
if (end !=1 && i-1&=START_I && maze[i-1][j] == 0) {
if (mazeChat(maze, i-1, j)==1) {
//四周都没有路
if (end !=1) {
maze[i][j] = 0;
方法调用：
if (mazeChat(maze, 0, 0) == 0) {
printf("没有通道");
printf("有通道\n");
路径会在后面的打印中根据我们预先设定的值去判断：
附上地址：
2.最短路径和计算：
【问题描述】: 给出一个矩阵，从左上角开始走，只能向右或者向下，所有数字累加就是路径和，求出其中最小路径。
{1,3,5,9},
{8,1,3,4},
{5,0,6,1},
先说一共有多少种走法:因为只能向右或者向下，所以数学方向考虑只有向右3次向下三次即可，所以简单的C6-3 即可
int uniquePaths(int m, int n)
int N = n + m - 2;
int K = n - 1;
double res = 1.0;
for (int i = 1; i &= n - 1; i++)
res = res * (N - K + i) /
return (int)
关于这个问题：
【问题描述】: 给出一个矩阵，从左上角开始走，只能向右或者向下，所有数字累加就是路径和，求出其中最小路径。
思路：只允许向右或者向下走 所以开始计算时当前s[i][j]只可能从s[i-1][j]+data[i][j]或者s[i][j-1]+data[i][j]计算得到
也就是s[i][j] = min(s[i-1][j],s[i][j-1])+ data[i][j] 即需要比较s[i-1][j],s[i][j-1])
因为第一行没有s[i-1][j]元素，只有s[i][j-1]元素。
第一列没有s[i][j-1]元素，只有s[i-1][j]元素。
需要特殊处理
我们通过比较每一个位置左边和上边大小而重新对该位置的值进行求和赋值即可得到一个全新的矩阵，取矩阵最后一个值即是我们需要的路径最短之和：
重新赋值矩阵方法：
//获取行数和列数
int rows = ROWS;
int cols = COLS;
for (int i = 1; i & i++)
data[i][0] = data[i - 1][0] + data[i][0];
for (int i = 1; i & i++)
data[0][i] = data[0][i - 1] + data[0][i];
//非第一行和第一列的元素
for (int i = 1; i & i++)
for (int j = 1; j & j++)
if (data[i][j-1] & data[i-1][j]) {
data[i][j] = data[i - 1][j] + data[i][j];
data[i][j] = data[i][j - 1] + data[i][j];
//返回最短路径值
return data[rows - 1][cols - 1];
拿到最小路径和的同时也可以通过得到的新矩阵去正推或者逆推得到路径下标的走法（这种重新赋值矩阵的方法优点在于只需要遍历一次即可拿到所有想要的结果，时间和空间复杂度低。缺点在于过程中存在的零时变量太多，所以之后得到新矩阵后才去获得路径下标）；
两种推算路径下标方法：
printf("最优路径坐标:\n");
int rowt = 3;
int colt = 3;
for (int i = 0; i
& 7; i++) {
printf("(%d,%d)\n",rowt,colt);
if(data[rowt-1][colt] & data[rowt][colt-1]){
int g = 0;
int k = 0;
for (int j = 0; j&7; j++) {
printf("{%d,%d}",g,k);
if (data[g][k+1] & data[g+1][k]) {
附上地址：
我喜欢写什么就写~
回溯算法 回溯法：也称为试探法，它并不考虑问题规模的大小，而是从问题的最明显的最小规模开始逐步求解出可能的答案，并以此慢慢地扩大问题规模，迭代地逼近最终问题的解。这种迭代类似于穷举并且是试探性的，因为当目前的可能答案被测试出不可能可以获得最终解时，则撤销当前的这一步求解过程...
动态规划（Dynamic Programming） 本文包括： 动态规划定义 状态转移方程 动态规划算法步骤 最长非降子序列（LIS） 最大乘积子串 Unique Paths Unique Paths II Minimum Path Sum Triangle 最长公共自序列...
计算机二级C语言上机题库（南开版） 1.m个人的成绩存放在score数组中，请编写函数fun,它的功能是：将低于平均分的人作为函数值返回，将低于平均分的分数放在below所指定的函数中。 2.请编写函数fun，它的功能是：求出1到100之内能北7或者11整除，但不能同时北7...
背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪：刷leetcode是什么样的体验？ 慢慢有一些赞和感谢, 备受鼓舞, 于是我把所做过的题目用一个script跑了一下，编辑成一篇文章。这个总结页面是这么规划的： 题目名称(答案...
本文翻译自TopCoder上的一篇文章： Dynamic Programming: From novice to advanced ，并非严格逐字逐句翻译，其中加入了自己的一些理解。水平有限，还望指摘。 前言 我们遇到的问题中，有很大一部分可以用动态规划(简称DP)来解。 ...
序 我经常都会收到一些同学在后台给我留言“哈迪，我想进入某某500强名企，这是我的简历，你能帮我看看么？” 很多时候我都没有回复这类同学。不是因为他们的问题太复杂，需要我花费大量时间回答。相反，答案其实很简单： “你的简历我看完了，其实你可以不用准备了，几乎没机会。” 为什...
针对单个引入文件设置onload属性 针对单个引入文件设置ng-init事件 通过$rootScope对象监听全局的$includeContentLoaded事件
六月中旬，在江城 酷夏刚刚开始 滂沱的大雨，拍打着檀香未燃的檐梢 在飞雕绘彩的尽头 当月光照出不洁的彷徨 唯有疏影在场 它测量过布达拉宫的经幡 也曾测量一颗心的长短 我在梦里无数次追逐 今夜依旧无功而返 何不为自己寻一座园圃 种上玫瑰和松柏 下雨时，用力拔下一根刺来 也不知...
人心生一念，天地尽皆知。 善恶若无报，乾坤必有私。 南无阿弥陀佛，我佛慈悲。
Requirements Gradle 2.5 only Android NDK r10e (if you are using NDK) SDK with Build Tools at least version 19.0.0 and we aim to minimize ...最大子矩阵问题实例解析
转载 &发布时间：日 16:22:22 & 作者：zinss26914
这篇文章主要介绍了最大子矩阵问题实例解析,分别列举了Java和C语言的相关实现,需要的朋友可以参考下
求一个M*N的矩阵的最大子矩阵和。
比如在如下这个矩阵中：
拥有最大和的子矩阵为：
其和为15。
首先，这个子矩阵可以是任意大小的，而且起始点也可以在任何地方，所以，要把最大子矩阵找出来，我们要考虑多种情况。
假定原始矩阵的行数为M，那么对于子矩阵，它的行数可以是1到M的任何一个数，而且，对于一个K行（K & M）的子矩阵，它的第一行可以是原始矩阵的第1行到 M - K + 1 的任意一行。
对于上面的矩阵，如果子矩阵的行数是2，那么它可以是下面几个矩阵的子矩阵：
在每一种情况里（我们这里有三种），我们还要找出一个最大的子矩阵，当然，这只是一种情况的最大子矩阵（局部最大），不一定是global最大。但是，如果我们知道每一种情况的最大，要找出global最大，那就小菜一碟儿了。
在讲在一个特殊情况下求最大子矩阵之前，先讲一个事实：
假设这个最大子矩阵的维数是一维，要找出最大子矩阵, 原理与求“最大子段和问题” 是一样的。最大子段和问题的递推公式是 b[j]=max{b[j-1]+a[j], a[j]}，b[j] 指的是从0开始到j的最大子段和。
Java实现示例：
假设原始矩阵为：[9，& 2， -6，& 2]， 那么b[] = {9, 11, 5, 7}, 那么最大字段和为11， 如果找最大子矩阵的话，那么这个子矩阵是 [9， 2]
求最大子段和的代码如下：
public int maxSubsequence(int[] array) {
if (array.length == 0) {
int max = Integer.MIN_VALUE;
int[] maxSub = new int[array.length];
maxSub[0] = array[0];
for (int i = 1; i & array. i++) {
maxSub[i] = (maxSub[i-1] & 0) ? (maxSub[i-1] + array[i]) : array[i];
if (max & maxSub[i]) {
max = maxSub[i];
&但是，原始矩阵可以是二维的。假设原始矩阵是一个3 * n 的矩阵，那么它的子矩阵可以是 1 * k, 2 * k, 3 * k，（1 &= k &= n）。 如果是1*K，这里有3种情况：子矩阵在第一行，子矩阵在第二行，子矩阵在第三行。如果是 2 * k，这里有两种情况，子矩阵在第一、二行，子矩阵在第二、三行。如果是3 * k，只有一种情况。
为了能够找出最大的子矩阵，我们需要考虑所有的情况。假设这个子矩阵是 2 *k, 也就是说它只有两行，要找出最大子矩阵，我们要从左到右不断的遍历才能找出在这种情况下的最大子矩阵。如果我们把这两行上下相加，情况就和求“最大子段和问题” 又是一样的了。
为了找出在原始矩阵里的最大子矩阵，我们要遍历所有的子矩阵的可能情况，也就是说，我们要考虑这个子矩阵有可能只有1行，2行，。。。到n行。而在每一种情况下，我们都要把它所对应的矩阵部分上下相加才求最大子矩阵（局部）。
比如，假设子矩阵是一个3*k的矩阵，而且，它的一行是原始矩阵的第二行，那么，我们就要在
里找最大的子矩阵。
如果把它上下相加，我们就变成了 4, 11, -10,1， 从这个数列里可以看出，在这种情况下，最大子矩阵是一个3*2的矩阵，最大和是15.
为了能够在原始矩阵里很快得到从 i 行到 j 行 的上下值之和，我们这里用到了一个辅助矩阵，它是原始矩阵从上到下加下来的。
假设原始矩阵是matrix, 它每一层上下相加后得到的矩阵是total，那么我们可以通过如下代码实现：
int[][] total =
for (int i = 1; i & matrix[0]. i++) {
for (int j = 0; j & matrix. j++) {
total[i][j] += total[i-1][j];
如果我们要求第 i 行到第 j 行之间上下值的和，我们可以通过total[j][k] - total[i-1][k] 得到, k 的范围从1 到 matrix[0].length - 1。
有了这些知识点，我们只需要在所有的情况下，把它们所对应的局部最大子矩阵进行比较，就可以得到全局最大的子矩阵。代码如下：
public int subMaxMatrix(int[][] matrix) {
int[][] total =
for (int i = 1; i & matrix[0]. i++) {
for (int j = 0; j & matrix. j++) {
total[i][j] += total[i-1][j];
int maximum = Integer.MIN_VALUE;
for (int i = 0; i & matrix. i++) {
for (int j = j & matrix. j++) {
//result 保存的是从 i 行 到第 j 行 所对应的矩阵上下值的和
int[] result = new int[matrix[0].length];
for (int f = 0; f & matrix[0]. f++) {
if (i == 0) {
result[f] = total[j][f];
result[f] = total[j][f] - total[i - 1][f];
int maximal = maxSubsequence(result);
if (maximal & maximum) {
C语言相关的实现
&&& 题目描述：&
&&& 已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。&
&&& 比如，如下4 * 4的矩阵&&
&&& 的最大子矩阵是&&
&&& 这个子矩阵的大小是15。&
&&& 输入：&
&&& 输入是一个N * N的矩阵。输入的第一行给出N (0 & N &= 100)。&
&&& 再后面的若干行中，依次（首先从左到右给出第一行的N个整数，再从左到右给出第二行的N个整数……）给出矩阵中的N2个整数，整数之间由空白字符分隔（空格或者空行）。&
&&& 已知矩阵中整数的范围都在[-127, 127]。&
&&& 输出：&
&&& 测试数据可能有多组，对于每组测试数据，输出最大子矩阵的大小。&
&&& 样例输入：&&
&&& 0 -2 -7 0&
&&& 9 2 -6 2&
&&& -4 1 -4& 1&
&&& -1 8& 0 -2&&
&&& 样例输出：&
#include &stdio.h&
#include &stdlib.h&
int main(void)
int i, j, h, k, n, max, sum, cur, matrix[101][101];
while (scanf("%d", &n) != EOF) {
// 初始化接收矩阵
for (i = 0; i & i ++) {
for (j = 0; j & j ++)
scanf("%d", *(matrix + i) + j);
// 动态规划(类似于一维数组连续最大子序列和)
max = matrix[0][0];
for (i = 0; i & i ++) {
// i，j确定上下界
for (j = j & j ++) {
for (k = i, sum = 0; k &= k ++)
sum += matrix[k][0];
if (sum & max)
for (h = 1; h & h ++) {
for (k = i, cur = 0; k &= k ++)
cur += matrix[k][h];
if (sum &= 0)
if (sum & max) max =
printf("%d\n", max);
大家感兴趣的内容
12345678910
最近更新的内容
常用在线小工具这是一篇旧文，点击以旧主题模式浏览。