DP Thinking Process
\n> How can we identify a rectangle?\nThe point on the top-left corner and the point on te bottom-right corner.\n\nFor each possible top-left\n  For each possib
\n> **How can we identify a rectangle?**\nThe point on the top-left corner and the point on te bottom-right corner.\n```\nFor each possible top-left\n  For each possible bottom-right\n    Check if matrix is made of 1s\n\t  If valid, we calculate area and update maxArea\n```\n\n> **How can we check if matrix with top-left (i, j) and bottome-right(x, y) is made of 1s?**\n> In Brute Force, we check each cells in matrix, that takes O(n^2) time complexity\n> To optimize, we observe that, \n```\nwith (i, j) as  top-left, rectangle with (x, y) as bottom-right is valid if \n  matrix[x][y] is 1\n  && rectangle with (x, y - 1) as bottom-right is valid\n  && rectangle with (x - 1, y) as bottom-right is valid\n```\n> We build an array isValid to save states. That takes O(1) time complexity.\n****\n```\n    public int maximalRectangle(char[][] matrix) {\n        if (matrix.length == 0) return 0;\n        \n        int rows = matrix.length, cols = matrix[0].length, maxArea = 0;\n        // For each point topleft\n        for (int i = 0; i < rows; i++) {\n            for (int j = 0; j < cols; j++) {\n                // Construt isValid\n                boolean[][] isValid = new boolean[rows][cols];\n                // For each point bottom right \n                for (int x = i; x < rows; x++) {\n                    for (int y = j; y < cols; y++) {\n                        if (matrix[x][y] != \'1\') continue;\n                        // Check if valid matrix\n                        isValid[x][y] = true;\n                        if (x > i) isValid[x][y] = isValid[x][y] && isValid[x - 1][y];\n                        if (y > j) isValid[x][y] = isValid[x][y] && isValid[x][y - 1];\n                        // If valid, calculate area and update max\n                        if (isValid[x][y]) {\n                            int area = (x - i + 1) * (y - j + 1);\n                            maxArea = Math.max(maxArea, area);\n                        }\n                    }\n                }\n            }\n        }\n        return maxArea;\n    }\n```\n**(\u4EBA \u2022\u0348\u1D17\u2022\u0348)** Thanks for voting!
['Dynamic Programming']