package leetcode;

/**
 * https://leetcode.com/problems/maximal-square/
 */
public class Problem221 {
    public int maximalSquare(char[][] matrix) {
        int max = Integer.MIN_VALUE;
        for (int row = 0; row < matrix.length; row++) {
            for (int col = 0; col < matrix[row].length; col++) {
                int x1 = col;
                int y1 = row;
                int x2 = x1;
                int y2 = y1;
                while (y2 < matrix.length && x2 < matrix[row].length) {
                    Square square = isSquare(matrix, x1, y1, x2, y2);
                    if (!square.square) {
                        break;
                    }
                    max = Math.max(max, square.val);
                    x2++;
                    y2++;
                }
            }
        }
        if (max == Integer.MIN_VALUE) {
            return 0;
        }
        return max;
    }

    private static class Square {
        boolean square;
        int val;

        public Square(boolean square, int val) {
            this.square = square;
            this.val = val;
        }
    }

    private Square isSquare(char[][] matrix, int x1, int y1, int x2, int y2) {
        int sum = 0;
        for (int row = y1; row <= y2; row++) {
            for (int col = x1; col <= x2; col++) {
                if (matrix[row][col] != '1') {
                    return new Square(false, sum);
                } else {
                    sum++;
                }
            }
        }
        return new Square(true, sum);
    }
}

@@ -162,129 +162,70 @@
  max
- = Integer.MIN_VALUE;%0A        for (int row = 0; row %3C matrix.length; row++) %7B%0A            for (int col = 0; col %3C
+Row = matrix.length;%0A        int maxCol = maxRow %3E 0 ?
  matrix%5B
 row%5D
@@ -220,27 +220,25 @@
  matrix%5B
-row
+0
 %5D.length
 ; col++)
@@ -233,32 +233,22 @@
 ngth
-; col++) %7B%0A     
+ : 0;%0A
         
    i
@@ -247,69 +247,88 @@
     
-   
 int 
-x1 = col;%0A                int y1 = row;%0A      
+answer = 0;%0A        Integer%5B%5D%5B%5D memo = new Integer%5BmaxRow%5D%5BmaxCol%5D;%0A
         
   in
@@ -327,191 +327,181 @@
     
-  
+for (
 int 
-x2 = x1;%0A                int y2 = y1;%0A                while (y2 %3C matrix.length && x2 %3C matrix%5Brow%5D.length) %7B%0A                    Square square = isSquare(matrix, x1, y1, x2, y2
+i = 0; i %3C maxRow; i++) %7B%0A            for (int j = 0; j %3C maxCol; j++) %7B%0A                answer = Math.max(answer, maximalSquare(matrix, maxRow, maxCol, i, j, memo)
 );%0A 
@@ -507,32 +507,34 @@
             
+%7D%0A
         
 if (!square.
@@ -525,144 +525,145 @@
     
-if (!square.square) %7B%0A                        break;%0A                    %7D%0A                    max = Math.max(max, s
+%7D%0A        return answer * answer;%0A    %7D%0A%0A    private static int maximalS
 quare
-.val);%0A        
+(char%5B%5D%5B%5D matrix, int maxRow, int maxCol, int row, int col,%0A
     
@@ -674,14 +674,13 @@
     
-x2++;%0A
+     
     
@@ -699,92 +699,92 @@
     
-y2++;%0A                %7D%0A            %7D%0A        %7D%0A        if (max == Integer.MIN_VALUE
+Integer%5B%5D%5B%5D memo) %7B%0A        if (row %3C 0 %7C%7C row == maxRow %7C%7C col %3C 0 %7C%7C col == maxCol
 ) %7B%0A
@@ -827,212 +827,199 @@
     
-return max;
+if (memo%5Brow%5D%5Bcol%5D != null) %7B
 %0A    
-%7D%0A%0A
     
-private static class Square %7B%0A        boolean square;%0A        int val;%0A%0A        public Square(boolean square, int val) %7B%0A            this.square = square;%0A            this.val = val
+    return memo%5Brow%5D%5Bcol%5D;%0A        %7D%0A        if (matrix%5Brow%5D%5Bcol%5D == '1') %7B%0A            int a = maximalSquare(matrix, maxRow, maxCol, row + 1, col, memo)
 ;%0A  
@@ -1028,241 +1028,233 @@
     
-%7D%0A
     
-%7D%0A%0A    private Square isSquare(char%5B%5D%5B%5D matrix, int x1, int y1, int x2, int y2) %7B%0A        int sum = 0;%0A        for (int row = y1; row %3C= y2; row++) %7B%0A            for (int col = x1; col %3C= x2; col++) %7B%0A                if (matrix
+int b = maximalSquare(matrix, maxRow, maxCol, row, col + 1, memo);%0A            int c = maximalSquare(matrix, maxRow, maxCol, row + 1, col + 1, memo);%0A            int min = Math.min(a, Math.min(b, c)) + 1;%0A            memo
 %5Brow
@@ -1264,17 +1264,14 @@
 ol%5D 
-!
 = 
-'1') %7B
+min;
 %0A   
@@ -1283,130 +1283,19 @@
     
-        return new Square(false, sum);%0A                %7D else %7B%0A                    sum++;%0A                %7D%0A            %7D
+return min;
 %0A   
@@ -1320,29 +1320,9 @@
 urn 
-new Square(true, sum)
+0
 ;%0A  

Update problem 221