Given a 2D binary matrix filled with 0‘s and 1‘s, find the largest square containing all 1‘s and return its area.
For example, given the following matrix:
1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0
Return 4.
public class Solution { public int maximalSquare(char[][] matrix) { //dp dynamic programing. 以当前点(x,y) = ‘1‘ 为右下角的最大正方形的边长f(x,y) = min( f(x-1,y), f(x,y-1), f(x-1,y-1)) + 1. //之所以将dp声明为[row+1][col+1]，主要防止对第一排和第一列特殊进行讨论 if(matrix==null||matrix.length<=0||matrix[0].length<=0) return 0; int row=matrix.length; int col=matrix[0].length; int res=0; int dp[][]=new int[row+1][col+1]; for(int i=0;i<row;i++){ for(int j=0;j<col;j++){ if(matrix[i][j]==‘1‘){ dp[i+1][j+1]=Math.min(dp[i][j],Math.min(dp[i][j+1],dp[i+1][j]))+1; res=Math.max(res,dp[i+1][j+1]); } } } return res*res; } }
原文：http://www.cnblogs.com/qiaomu/p/4711825.html