二维数组最大面积的问题（动态规划）

actionzhang

发布于 2022-11-30 16:57:12

4000

发布于 2022-11-30 16:57:12

文章被收录于专栏：action的经验之路

今天遇到一个问题：

给定一个二维数组，数组中的元素只有0和1，求面积最大的全1方阵的面积（就是矩阵内包含的全是1）。如图

红色的部分就为面积最大的方阵（方阵内元素都是1）。

我们可以新建一个矩阵，和原来的矩阵同样大小，但是这个矩阵内元素是存储着，以当前元素为方阵最右下角的元素的最大面积，像是上图中红色的那个方阵，右下角元素，就存着这个方阵的面积，但是这个元素的大小怎么求，是我接下来要讲的，新矩阵的元素是这么填充的，取这个元素的上方元素，左方元素，对角线元素，这几个元素都存着的是面积，如果将面积映射为01矩阵的话是不是应该有一个交集，如下图

现在要求以红色圆圈为有下角元素的最大方阵面积，那么此元素的左方元素的最大面积应该是深蓝色方框内的方阵的面积，上方最大面积应该是红色方框内的面积，对角元素的最大面积应该是浅蓝色方框内的面积，那么黑色方框内的方阵就是我们要求的最大面积，大家请看红色方框和看蓝色方框内的区域完全包含在黑色方框内，也就是说要求的方阵是不是比完全包含在黑框方阵内的区域（浅蓝色和红色方框），多一行一列啊，图画多了就会发现，要求的方阵的区域只会包含左，上，对角三个区域中最小的一个区域也就是，面积最小的区域，那么这个区域的边其实就是比要求区域的边短1，所以求出最小的面积，技能就去最小面积的边，那么就能求出要求的面积。那么新的矩阵每个元素就都可以算出来，所以最大面积应该就存储在这个新的矩阵内，所以从此矩阵取出最大元素就是，最大的面积。这就是运用了动态规划的思想。这道题很巧妙，需要想想，下面是我的代码，有兴趣的人可以看看，谢谢！！！

package com.test;

public class Main {

	public static int getMaxArea(char[][] area){
		if(area==null||area.length==0){
			return 0;
		}else{
			int max=0;
			int[][] maxArea=new int[area.length][area[0].length];
			if(area[0].length==0){
				return 0;
			}else{
				for(int i=0;i<area.length;i++){
					for(int j=0;j<area[i].length;j++){
						if(i==0||j==0){
							maxArea[i][j]=area[i][j]-'0';
							if(maxArea[i][j]>max){
								max=maxArea[i][j];
							}
						}else if(area[i][j]=='0'){
							maxArea[i][j]=0;
						}else{
							int length=Math.min(maxArea[i-1][j-1], Math.min(maxArea[i-1][j], maxArea[i][j-1]));
						    int nowArea=(int)Math.pow(Math.sqrt(length)+1, 2);
						    maxArea[i][j]=nowArea;
						    if(nowArea>max){
						    	max=nowArea;
						    }
						}
					}
				}
				return max;
			}
		}
	}
	
	public static void main(String[] args) {
		//char[][] test=new char[][]{"110".toCharArray(),"111".toCharArray(),"111".toCharArray()};
		char[][] test=new char[][]{"1".toCharArray()};
		System.out.println(getMaxArea(test));

	}

}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2015-07-10，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法