Maximal Square

https://leetcode.com/problems/maximal-square/
给定一个二维数组，里面包含0和1，求出由1围起来的正方形的最大面积
Input:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Output: 4

解法---DP

二维数组DP，dp[i][j]代表以i，j为右下角的正方形，最长的边长
那么DP的递推方程可得：
dp[i][j] = min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1]) + 1
注意当i或者j为0的时候，dp[i][j]的值特殊处理

talk is cheap,show me your example

image.png

上代码

    public int maximalSquare(char[][] matrix) {
      int rows = matrix.length, cols = rows > 0 ? matrix[0].length : 0;
        int[][] dp = new int[rows][cols];
        int maxsqlen = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = matrix[i][j] - '0';
                } else if (matrix[i][j] == '1') {
                    dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;
                }
                maxsqlen = Math.max(maxsqlen, dp[i][j]);
            }
        }
        return maxsqlen * maxsqlen;
    }

参考文献：https://leetcode.com/problems/maximal-square/solution/