# Maximal Square

## Question

### Problem Statement

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.

## 题解

dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1; if matrix[i][j] == 1
dp[i][j] = 0; if matrix[i][j] = 0


### Java

public class Solution {
/**
* @param matrix: a matrix of 0 and 1
* @return: an integer
*/
public int maxSquare(int[][] matrix) {
int side = 0;
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return side;
}

final int ROW = matrix.length, COL = matrix[0].length;
int[][] dp = new int[ROW][COL];
for (int i = 0; i < ROW; i++) {
dp[i][0] = matrix[i][0];
side = 1;
}
for (int i = 0; i < COL; i++) {
dp[0][i] = matrix[0][i];
side = 1;
}

for (int i = 1; i < ROW; i++) {
side = Math.max(side, matrix[i][0]);
for (int j = 1; j < COL; j++) {
if (matrix[i][j] == 1) {
dp[i][j] = 1 + minTri(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]);
side = Math.max(side, dp[i][j]);
}
}
}

return side * side;
}

private int minTri(int a, int b, int c) {
return Math.min(a, Math.min(b, c));
}
}