Solution.java

import java.util.*;
public class Solution {

    public int maximalRectangle(char[][] matrix) {
        int n = matrix.length;
        if (n == 0) return 0;
        int m = matrix[0].length;
        if (m == 0) return 0;

        int[][] sum = new int[n][m];
        for (int j = 0; j < m; j++) {
            int curr = 0;
            for (int i = 0; i < n; i++) {
                if (matrix[i][j] == '1') {
                    curr++;
                } else {
                    curr = 0;
                }
                sum[i][j] = curr;
            }
        }
        // printMatrix(sum, n);
        int ret = 0;
        for (int i = 0; i < n; i++) {
            ret = Math.max(ret, largestRectangleArea(sum[i]));
        }

        return ret;
    }

    public int largestRectangleArea(int[] height) {
        Stack<Integer> stack = new Stack<Integer>();
        int i = 0;
        int maxArea = 0;
        int[] h = new int[height.length + 1];
        h = Arrays.copyOf(height, height.length + 1);
        while (i < h.length) {
            if (stack.isEmpty() || h[stack.peek()] <= h[i]) {
                stack.push(i++);
            } else {
                int t = stack.pop();
                maxArea = Math.max(maxArea, h[t] * (stack.isEmpty() ? i : i - stack.peek() - 1));
            }
        }
        return maxArea;
    }

    public void printMatrix(int[][] mat, int n) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.format("%d ", mat[i][j]);
            }
            System.out.format("\n");
        }

    }
    public static void main(String[] args) {
        String[] inp = {"1111111110111111111101111111111111101011110111111111111111111111111111001011111011111111111111111111", "1111111110111111111111111011111110111111111011011111111111111111111111111110111101101111110111111011", "1111111111101101111110111111111111111111111011110111111111110111111111111111111111111111111111111001", "1111111111111111111111111111111111111110111011110111111111111111111111111111011111111110110111111111", "0111111111111101111111111111111111111111111110111110110111111111111111110110111111110111111111111100", "1111111111111111111111111101111111111011111101111111111111111111111111011110111111111111111101111111", "1101111111111111111111111101111111111111111111111111111111111111011111111111111111111110001111111111", "1111111111110111011111111101111011111011111111111111111111111111111111111111101111111111011111111011", "1101111111111111111111101111111111101111111111111111111110101101111011111111111111111101111111111111", "1111111101111101101111111111111011101111110110111111111111111101011111111111110111111111011111111111", "1111111111011101111111111111011111110111111111111111111011111111111111111111111111111111111111111110", "1111110101111111111110111111101111111111111111111011111111111111011111101110111110111111111111110111", "1011111101111111101111111111111111011111101101111111111111111111111111111111111011111111111111111010", "1111011111111111111111111111111111111111111111011111111111111111111111111101111111111111111011111111", "1111111111111111111111110111111111111010111111111011110111101111111011111011111111111101111111101111", "1111111111110111111111111111111111111111111111111010011111101111111111110111111111111111111111101111", "1111111111111111111111100111111111111111111111111111111111111111111111101111111111111111111101111111", "1101111111011111011111111111111111111111111111111110111110111101111111111011111111111101101011111111", "1111111111111111111111111011111111111111111111111111111111111111111101111111110111111111111111111111", "1110111111111111110111111011011111111101110111111111001111111111111011111111101111111111101110111011", "1011111111111101101111111011111111110011111111111111111111111110111111111111111111111110111011110111", "1110111111111111111111111111111110111111111111111111111111111111011111111111111111111111111111111111", "1101111111111010111111110011111111011011111101111111111101101111111111111110111011111111111111111111", "1111111101111111011101111111111101111100111111111111111011111111111111111111111101110111101111111111", "1111110111111011011111111111111111111111111111111111111111011101111111101101111111101111110111111111", "1111111111111101111111111111101011111111111111111111101111011111111111111111111111111111111111110111", "1111011111111111110111111111101111011100111111111111101101101110111111111110111111111111111011111111", "1111111111111111111111111111110101111101111011111111101111111101111111111111111110111111111111111111", "1111111101110011111111111111111111110111111111111111111111111111111111111111111111001111111111111111", "0111110111111111111111111111111111111011111011111111111110111011111101011111111111111111111111111111", "1111111111111111011111111011111111111111111111111111011111111101111111111111111111111111011011111111", "1111111101111111111101111011111111111111111111111111111111111111111011111111110111011111111111111111", "1110111111011111101101101011111111110111111111111111101110110100111111111111111111111111111111111101", "1111111111111111111111111111111111111111111011111101111111011111111101111101111111111111111101111111", "1110111111100111111111111111111111111111011111111111110111110111111111111101111111111111111111111111", "1111111111111110111111111111111111110111111101111111110111101111111111111011110111110101101111111111", "1111110111111111111111111111111111111111111110011111111111111111111111111111110011011111101111111110", "1111111111111111111110101110011111111001111111111101101111111111111111111111111111111111111110111111", "1110111111011110111011111111111111111111111111111111111111111010111111111001110111111111011111011111", "1011111111111111111111111101111111111111111111111111111111111111111111111111111011111111111111101111", "1111111111111111111111111111111101111111111111111110111111111111110111111111111111111001111110111111", "1111110111101111111111111111111100111111111111111101011111111111110101111111111111011111111011101111", "1110111111111111101111111111111110111111110111110111101111111111111111111111111111101111111111111111", "1111111111111111111111011111111111111111111010111111111111111111111110111111111111111111110011111111", "1010111111111011111111111111111111111111111111011101111111111111111111101111111111111011111111111101", "1111111111011111111111111111111111111111111111111111111111111111111111111111110111111111111111111111", "1111111110111111110011011111111110111111111101111110111111111111011111111111101011001111001101111111", "1111111111111111111111111011111111111110101111111111111111111111111111111111111111111111111111111111", "1111111111110111111111111101011111111111111111111110111111111111110111111111111011111111110111111011", "1110111011110011111111011111111111111110111111111111101110111111111111111111111111111111110111111111", "0101111111111111110110111111111111111111111111111111101111111111111101101011111111110111111111111111", "1011110111011111111111111111111111111111110111110111111001111111111111111111001111111111111111101111", "1111110111111111111111111110111111111111111111111111101111111111111111101111111111111011111111011110", "1111011111111111111111101110111101111111111111111111111111111111110111111111111111101111111111011111", "1111111111111111111111111111111111111111111011111111111111111111111111111110011111111111111111111111", "1111111111111111111111111101111101111111111111111110111111111111111111111111111111111111100111111111", "0011111111111111111111111111011111111101111111111111111111111111111111111111111111111111111111111111", "1111111110111111111111111111111111011111111111111110111111111111111101111111111111111111101111111111", "1111111111101111011111111111011110111111011111111101111111111110111111111111111110111011111111110111", "1111111111110111111111111111111111111110101111111111111111111111111111111101011111111101101101111011", "1111111111111111101111111111101110101110111111111111111111110111111111111111111111101111111111111111", "1111111111011111111111111111111101111110111111110111111111111111111111101101111111111111111111111111", "0111110111011111111111111101011101100111111011101111011111011111111111111101111110111111111111111011", "1111111111110101111111111111111111110111111111111111111110111111101111111111111111111011111111111111", "1111101111111011110111111111111111111111101111111111111111111111110111111111011111111111111101111111", "1111111101111111111111111111111001111111111011111111111111111011111111111111110011011111111111111111", "1111111111111111111111111111111111111111111111011101111111111111101111111101011111111101111111111111", "1111101101111111111111111111111111110110011111111111111111111101111110111111111111111111111111111111", "1111111111111111111111110111111101111110111011111111101011111011111110111111111111101111111111111111", "1111111111101111100111010111111110011111110110111111111011111111111101111111111111111101111111110111", "1111111111111111101111111111111111111111111111101111011111111111111111111111111111111101111111111111", "1111111101111111111111111111111111110110111111111101101111111111111111111011111111111111111101111011", "1101111111111111111111111110110101111111111111111111111111111111111110011101111111100111111111111110", "1111111011111111101111110111111111111111111101111111111101101011111011111111111111111111111111111111", "1111011111110111111111011111111111011111111111111111111111111111111111111110111111111111011111111111", "1111111111111111111111111111111011111111110111111110111111111101111111111111111011011111111111111111", "1111111110111111111111111111111110111111111111111111101111111111111111111111111111111101111110100111", "1111011111111111110111111111111111110111011111111111110111111111111111011111111111111111111111110111", "1011111111111100111101111111111111101111111111111111111111111111111111110011111111111111111111111101", "1111111011111111111111110111111111111110111011111111111101111111111111111111111111111111111111111111", "1101111111111111111111111111111111111111111111111100011111111110101111111111101111111111111111111111", "1111001111111111111111101111111111111111111111111111111111111111111111111111111111110111111111111111", "1111111101111111111111111111111011111111111111111111111111111111011111110011111101111111011111111111", "1110111111111101111111111101111111111111111111111111111111011111111001110111111011111011111111111111", "1111111001111111110111111110111111111111111011111111111111111111111111110111111111111111111111111111", "1011111111111111110101101101111111111011111111111111011111110111111011111111111111011111111111111111", "1101111111111110110011101111111111101111110111110111111111101111111101110111111111111111100111111111", "0111111110111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111", "1111111111111110111101111111111111111111111111111111111111011011111111111101101011111111111111111111", "1111101111111111111011111111111111111111110111111101111110111111111011111111111111111111111111111111", "1111111101111111011111111111110111111111111111111111011110101111011111111011111011011111111111111111", "1101111111111111101111111111111111111111011001111111111111111111111111111111111111111111111111111011", "1111111111111101111110111111011111111111111111111111111111110111111111111111111111111111111011111111", "1111110110111111111111111101111111111111111111111111111111111111111111111111111110011111101111111111", "1110111111111111111111111111111111111111111111111111111011111111111111111111111111011111111111111111", "1110111101111011110111111101111111111111111111111111111111111111111111111111110111110111111111111111", "0011111111110111111111110011111111111101111111101111111111100111001111110111111111111111111111111111", "1111111011111111111101111111111111111111111110110111111111111111111111111111111101101111111011111111", "1111011111111111101111111111111111111111000111111111111111111011111111111111011111111101011111111111", "1111111111111111011111111111111111111111111111111111111111111111111111011111111101110111110111111111"};
        // String[] inp = {"00", "11"};
        int n = inp.length;
        int m = inp[0].length();
        char[][] data = new char[n][m];
        for (int i = 0; i < n; i++) {
            data[i] = inp[i].toCharArray();
        }

        // for (int i = 0; i < n; i++) {
        //     for (int j = 0; j < n; j++) {
        //         System.out.format("%c ", data[i][j]);
        //     }
        //     System.out.format("\n");
        // }
        Solution s = new Solution();
        int res = s.maximalRectangle(data);
        System.out.format("%d\n", res);
    }
}