- 浏览: 42098 次
- 性别:
文章分类
最新评论
子矩阵问题
- 博客分类:
- leetCode-dp
- 经典算法问题
矩阵中的最大正方形子矩阵(Maximal Square)
题目描述:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
比如说,在这个矩阵中,由1构成的最大正方形子矩阵就是4.1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
题目分析:
matrix[ ][ ] 用来存放01,那么当求矩阵[i][j] 的最大矩阵时,用一个 max存放正方形的边长
如果[i][j] == 0 , 那么最大正方形边长就等于max,
如果[i][j] == 1 , 那么,就要看它的[i-1][j] , [i -1][j-1] , [i][j -1] , 取他们中的最小值 , 然后加1 就是
[i][j] 能够成的最大矩阵,最后与max , 比较,更新最大边长。
递推公式:
m[i][j] = min(m[i-1][j] , m[i][j-1] , m[i-1][j-1] ) + 1; matrix[i][j] = 1 m[i][j] = 0 ; matrix[i][j] = 0; m为中间矩阵
public class Solution { // 返回最大的正方形 public int maximalSquare(char[][] matrix) { if(matrix == null) return 0; int rows = matrix.length; if(rows == 0) return 0; int cols = matrix[0].length; int[][] m = new int[rows+1][cols+1]; int max = 0; for(int i = 1 ; i <= rows; i++) { for(int j = 1 ; j <= cols ; j++) { if(matrix[i - 1][j - 1] == '0') { m[i][j] = 0; continue; } m[i][j] = (Math.min(Math.min(m[i - 1][j] , m[i][j-1]) , m[i - 1][j - 1] ) )+ 1; max = Math.max(max , m[i][j]); } } return max * max; } }
最大子矩阵和
N*N的矩阵中,求最大子矩阵的和?
先不要往动态规划上想,如果暴力的求解最大子矩阵该怎么求?
假如给你一个3x3的矩阵 matrix:
那么最大矩阵就可能在 :
第1行中,1 2 行中 ,1 2 3 行中
或者 第2行中,2 3 行中
或者 第3行中 ----------- 这里就构成了下面代码外面的两层for循环
可是光知道在那些行中,还不能够求出矩阵和啊。这样就得遍历所有列
求出 i 到 j 行, k 到 m 列的矩阵和,到了这一步,就可以把求最大子矩阵和的过程化成了
求连续子数组的最大和。是不是一样的道理!遍历每一列求和sum,不就是等同于移动数组的下标就和?
然后把求的sum与之前的比较,如果大于则更新。然后,sum再与max比较,大于则更新max.
过程是这样,但是这道问题难点就在于怎么求 i 到 j 行, k 到 m列的矩阵和?
在下面的代码中,通过建立一个中间矩阵p , p[i][j] 就表示[1][1] 到 [i][j] 的矩阵和。
p[i][j] 就表示 1 到 i 行 , 1 到 j 列 构成的这个子矩阵中所有元素的和。
比如说一个下面矩阵: p[1][1] = 2 , p[2][2] = 2+3+(-2)+3 = 6
2 3 4
-2 3 5
0 -1 4
所以 , 就可以得到求p[i][j] 的公式:
p[i][j] = p[i-1][j] + p[i][j-1] - p[i-1][j-1] + a[i][j]具体这个公式,怎么理解,画图!!! 很好理解的。
p[i][j] 就是一个中间矩阵,有了它,就可以很轻松的求得 i 到 j 行, k 到 m 行的 的 sum 了。
下面是公式:// 还是画图理解。
sum = p[j][m] - p[j][k-1] - p[i-1][m] + p[i-1][k-1]
int maxMatrixSum(int[][] a) { int n = a.length; int m = a[0].length; int[][] p = new int[n+1][m+1]; // 初始话p , 由矩阵a , p[i][j] 公式求得p中每一项的值 for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) p[i][j] = p[i-1][j] + p[i][j-1] - p[i-1][j-1] + a[i - 1][j - 1]; } for(int i = 1 ; i <= 3 ; i++) { System.out.println(Arrays.toString(p[i])); } int max = 0; for (int i = 1; i <= n; ++i) { for (int j = i; j <= n; ++j) { // 这里的逻辑就是求连续子数组的最大和了。 int sum = 0; for (int k = 1; k <= m; ++k) { int temp = p[j][k] - p[j][k-1] - p[i-1][k] + p[i-1][k-1]; if (sum > 0) sum += temp; else sum = temp; if (sum > max) max = sum; } } } return max; }
发表评论
-
头尾指针
2015-06-18 11:11 3101. 三数和 3SUM ... -
两个有序数组合并找第k个元素
2015-06-12 17:51 474暴力求解 : O(m + n) ... -
字符串相关算法
2015-06-10 22:53 0最长公共子串 : 1. 子串与子序列的区 ... -
逆序对问题 (O(nlgn))
2015-05-11 18:37 430问题描述 在数组arr[]中, ... -
目录备忘
2015-05-01 13:37 374该目录下主要收集一些经典的算法问题, ... -
unique Binary Tree
2015-04-30 14:42 360第一种 : 给定一个数 ... -
Wildcard Matching
2015-04-29 14:30 398'?' Matches any single charact ... -
leetcode Stock买 and 卖
2015-04-27 23:09 382在数组中求最大的差值 最大的差值和 两对差值最大 ... -
关于连续子数组的最大和和最大积
2015-04-23 19:43 577Find the contiguous subarray ... -
Decode Ways
2015-04-23 16:07 317A message containing letters f ... -
Unique Paths
2015-04-22 13:03 278A robot is located at the top ... -
Climbing Stairs
2015-04-22 11:21 350You are climbing a stair case. ... -
word break
2015-04-20 11:21 319Given a string s and a dic ... -
House Robber
2015-04-07 14:12 512You are a professional rob ...
相关推荐
最大子矩阵指的是在一个矩阵中找到一个子矩阵,使得该子矩阵的元素...通常情况下,最大子矩阵问题可以通过动态规划或者分治算法来解决。找到最大子矩阵有助于解决一些实际问题,比如在图像处理中找到最大的连通区域等。
最大子矩阵
问题: 求一个M*N的矩阵的最大子矩阵和。 比如在如下这个矩阵中: 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 拥有最大和的子矩阵为: 9 2 -4 1 -1 8 其和为15。 思路: 首先,这个子矩阵可以是任意大小的,...
最大子矩阵
最大子矩阵和问题.pdf最大子矩阵和问题.pdf最大子矩阵和问题.pdf最大子矩阵和问题.pdf 详细分析和源码 值得好好研究啊
最大子矩阵是指在一个二维矩阵中,找到...最大子矩阵问题可以被看作是最大子数组问题的二维版本。最大子数组问题是在一个一维数组中,找到一个具有最大和的连续子数组。在一维情况下,可以使用动态规划或分治算法来解决
该代码具体实现了对于最大子矩阵问题利用动态规划的思路解决。
问题:给定N×N矩阵,矩阵元素都是-127到+127之间的整数。请找到一个子矩阵,使得其元素之和最大。 输入: 第一行整数 N (N)。接下来N行元素,每行N个元素,每个元素介于-127到127之间。
问题:给定1×N的单行矩阵,矩阵每个元素都是-127到+127之间的整数。请找到一个连续子矩阵,使得其元素之和最大。 输入:整数 N (N),及N个元素。
最大子矩阵问题是一个经典的优化问题,其目标是在一个给定的矩阵中找到一个子矩阵,使得该子矩阵的元素和最大。这个问题可以看作是一维最大子序列和问题的扩展,从一维变为了二维。
用于求解最大子矩阵问题的一个程序,运用了动态规划,是最大字段和的升级版
最大子矩阵 C++实现的最大子矩阵和 C++实现的最大子矩阵和 C++实现的最大子矩阵和 C++实现的最大子矩阵和 C++实现的最大子矩阵和 C++实现的最大子矩阵和
最大子矩阵
二维数组首尾相连,上下也相连,像个游泳圈或轮胎,又如何求最大子矩阵和? 如游泳圈展开成3行3列的二维矩阵: -18 10 7 1 -20 2 1 38 -2 那么最大的子矩阵和为:10+7+38-2=53 2 10 7 1 -20 2 1 38 -2 那么最大...
最大子矩阵
最大子矩阵最大子矩阵.pdf最大子矩阵.pdf
C++求最佳子矩阵代码,采用遍历子矩阵的方法,求最大子矩阵(最佳区域)
最大子矩阵最大子矩阵.zip最大子矩阵.zip
求全0子矩阵个数matrix(vc++)