最大正方形

在一个二维01矩阵中找到全为1的最大正方形

您在真实的面试中是否遇到过这个题？ 

Yes

样例

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

返回 4

题目地址

动态规划的办法，我们可以先求出正方形最大的边长，我们推导出的公式是,原来的数组是arr[][];
f[][]是存储结果的表，当最大正方形包括arr[i][j]的时候，f[i][j] = min(f[i-1][j-1],f[i][j-1],f[i-1][j])+1;当不包含f[i][j]的时候，f[i][j] =0;此时 最大的边长为num = max(f[i][j],num)

完整代码如下：

package lintcode;

import java.util.Scanner;

/**
 * Created by Taoyongpan on 2017/11/15.
 * 436,在一个二维01矩阵中找到全为1的最大正方形
 * 动态规划的思想
 * 求出正方形最长的边长
 */
public class MaxSquare {

    public static int SquareMax(int[][] arr){
        int n = arr.length;
        int m = arr[0].length;
        int num = 0;
        int[][] f = new int[n+1][m+1];
        if (n<=0||m<=0){
            return num*num;
        }
        //初始化f数组
        for (int i = 0;i<n;i++){
            f[i][0] = arr[i][0];
            num = Math.max(f[i][0],num);
        }
        for (int j = 0; j<m;j++){
            f[0][j] = arr[0][j];
            num = Math.max(f[0][j],num);
        }

        for (int i = 1;i<n;i++){
            for (int j = 1;j<m;j++){
                if (arr[i][j]==1)
                    f[i][j] = Math.min(Math.min(f[i-1][j-1],f[i][j-1]),f[i-1][j])+1;
                else
                    f[i][j] = 0;
                num = Math.max(f[i][j],num);
            }
        }
        return num*num;
    }
    //主函数
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[][] arr = new int[n+1][m+1];
            for (int i = 0 ;i<n;i++){
                for (int j = 0;j<m;j++){
                    arr[i][j] = sc.nextInt();
                }
            }
            System.out.println(SquareMax(arr));
        }
    }
}