Problem

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.

Example

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.

Note

类似这种需要遍历矩阵或数组来判断True or False，或者计算最优解（最短步数，最大距离，etc）的题目，都可以使用递归。
所以，找矩阵内存在的最大正方形，需要：

1. 构造传递方程：用dpi存储以当前点matrixi作为正方形右下角顶点，所存在的最大正方形的边长，由matrixi左、上、左上三点的dp值共同判定；

2. 初始化边界：matrix的第一列和第一行；

3. 自顶向下递推dp并更新max，找到max的最大值求平方得最优解。

Corresponding dp matrix:

0 0 0 0 0 0 
0 1 0 1 0 0
0 1 0 1 1 1
0 1 1 1 2 2
0 1 0 0 1 0

mLen = 2, the maximum dp[i] = 2 appeared twice, indicating that there are two maximal squares.

Solution

public class Solution {
    public int maxSquare(int[][] matrix) {
        int mLen = 0;
        int m = matrix.length, n = matrix[0].length;
        int[][] dp = new int[m+1][n+1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (matrix[i-1][j-1] == 1) {
                    dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1]))+1;
                    mLen = Math.max(mLen, dp[i][j]);
                }
            }
        }
        return mLen * mLen;
    }
}