[LeetCode] Maximal Rectangle

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

[Solution].java

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if(matrix == null || matrix.length < 1 || matrix[0].length < 1) return 0;
        int[][] dp = new int[matrix.length + 1][matrix[0].length + 1];
        int max = 0;
        for(int row = 1; row < dp.length; row++){
            for(int column = 1; column < dp[0].length; column++){
                if(matrix[row - 1][column - 1] == '1'){
                    dp[row][column] = dp[row - 1][column] + 1;
                    int high = dp[row][column];
                    if(high > max) max = high;
                    int left = column - 1;
                    while(dp[row][left] != 0){
                        high = Math.min(high, dp[row][left]);
                        int area = high * (column - left + 1);
                        if(area > max) max = area;
                        left--;
                    }
                }
            }
        }
        return max;
    }
}