`

子矩阵问题

 
阅读更多
 
 矩阵中的最大正方形子矩阵(Maximal Square)  
  题目描述:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
    比如说,在这个矩阵中,由1构成的最大正方形子矩阵就是4.
   题目分析:
    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;  
	}  
 
    
分享到:
评论

相关推荐

    浅谈最大子矩阵问题.docx

    ### 最大子矩阵问题概述 #### 一、问题定义及应用场景 最大子矩阵问题是指在一个给定的矩阵中寻找一个子矩阵,使得该子矩阵内元素的和达到最大值。这种问题不仅在理论计算机科学中占有重要地位,而且在实际应用中也...

    最大子矩阵问题介绍.zip

    在计算机科学和算法领域,"最大子矩阵问题"是一个经典的线性代数和数组处理问题。它涉及到寻找一个二维矩阵中的连续子矩阵,使得该子矩阵的所有元素之和达到最大值。这个问题在许多实际应用中都有所体现,比如在数据...

    最大子矩阵问题实例解析

    最大子矩阵问题是一个经典的计算机科学问题,主要涉及矩阵计算和动态规划。问题的目标是在一个M*N的矩阵中找到一个子矩阵,使得其所有元素之和最大。这个问题在算法设计和数据结构领域有广泛的应用,例如在图像处理...

    揭秘最大子矩阵问题:算法解析与应用实践.txt

    最大子矩阵

    MaxSum.rar_最大子矩阵

    【最大子矩阵问题】在计算机科学中,是一个经典的算法问题,属于数组处理和最优化的范畴。该问题的目的是在给定的二维矩阵中找出一个子矩阵,使得其所有元素之和最大。这个问题可以视为一维最大子序列和问题(如 ...

    最大子矩阵和问题.pdf最大子矩阵和问题.pdf

    ### 最大子矩阵和问题详解 #### 一、问题背景与定义 在计算机科学与算法设计领域中,最大子矩阵和问题是寻找一个给定矩阵中具有最大和的子矩阵的问题。这类问题通常出现在数据挖掘、图像处理以及机器学习等领域,...

    最大子矩阵应用场景介绍.zip

    最大子矩阵问题是一个经典的问题,它在许多实际应用中都有广泛的应用。这个问题涉及到寻找一个矩形子矩阵,使得其所有元素的和达到最大值。 一、最大子矩阵问题的定义 最大子矩阵问题是指给定一个MxN的矩阵,找出...

    最大子矩阵.最大子矩阵ppt

    最大子矩阵问题通常指的是在一个二维矩阵中寻找一个子矩阵,使得该子矩阵的元素之和最大。这类问题在计算机科学和算法设计中具有重要的应用价值,尤其是在数据挖掘、图像处理等领域有着广泛的应用前景。最大子矩阵...

    最大子矩阵-使用C++实现的最大子矩阵求和.zip

    在计算机科学中,最大子矩阵问题是一个经典的线性代数问题,主要涉及到数组处理和动态规划。本问题的目的是寻找给定二维矩阵中元素之和最大的连续子矩阵。这个问题有多种解决方案,其中一种高效的方法是Kadane's ...

    最大子矩阵概述.pdf

    ### 最大子矩阵问题概述及解决方案 #### 一、问题定义与背景 **最大子矩阵问题**是指在给定的一个二维矩阵中寻找一个连续子矩阵,使得该子矩阵的元素和达到最大值。这一问题源自于经典的**最大子数组问题**,即在...

    C++求最佳子矩阵代码

    在编程领域,子矩阵问题是一种常见的优化问题,特别是在数据分析、图像处理和算法竞赛中经常遇到。本主题聚焦于使用C++解决这个问题,特别是寻找最佳子矩阵,即具有最大和的子矩阵。这个问题的核心是找到一个矩阵中...

    最大子矩阵.zip最大子矩阵.zip

    最大子矩阵问题的一个常见实例是求解"最大连续和子矩阵",也称为“最大矩形和”。这要求找出矩阵中元素之和最大的连续矩形区域。例如,如果矩阵中的每个元素代表一个位置的温度,我们可能想要找出温度总和最高的连续...

    最大子矩阵动态规划详解.zip

    本主题将深入探讨一个特定的应用场景:最大子矩阵问题。这个问题涉及到如何在给定的矩阵中找到具有最大和的连续子矩阵。 首先,我们需要理解什么是矩阵。在数学中,矩阵是一个矩形阵列,由有序的元素(通常是数字)...

    python举例什么是最大子矩阵

    在Python编程中,最大子矩阵问题是一个经典的计算机科学问题,主要涉及到数组处理和动态规划算法。这个问题的目标是在一个二维矩阵中找到一个子矩阵,它的所有元素之和是最大的。这在许多实际应用中都有所体现,例如...

    最大子矩阵和.docx

    1. **最大子段和问题**:在解决最大子矩阵问题之前,先理解最大子段和问题是非常重要的。给定一个数组`a[1..n]`,目标是找到数组的一个连续子段,使得该子段的元素之和最大。这个问题可以通过动态规划的方法解决,...

    最大子矩阵.pdf最大子矩阵.pdf最大子矩阵.pdf

    最大子矩阵问题是指在给定的二维矩阵中寻找一个子矩阵,该子矩阵的元素之和达到最大值。这是一个经典的计算机科学与数学问题,在算法设计与分析领域具有重要意义。 ### 最大子矩阵的概念 在计算机科学和数学领域,...

    最大子矩阵解析及示例动态规划处理优势.txt

    最大子矩阵问题是一个在计算机科学领域内非常经典且重要的优化问题。它的主要目标是在一个给定的矩阵中寻找一个子矩阵,使得该子矩阵内的所有元素之和达到最大。这个问题可以被视为一维最大子序列和问题的一个自然...

    MaxSubMat_最大子矩阵_算法设计_动态规划_

    最大子矩阵问题是一个经典的计算机科学问题,主要涉及矩阵计算与算法设计,特别是动态规划的应用。在数据结构和算法的学习中,解决这类问题的能力是衡量一个程序员能力的重要指标。本问题的目标是找到一个矩阵中元素...

Global site tag (gtag.js) - Google Analytics