Evidently the most common question asked by google (reference Leetcode). I can only figure out a N^3 solution... :/

maximalRectangle.py

class Solution:
    def __init__(self):
        self.memoized = {}
        self.call_count = 0

    def areaPoints(self, point1, point2):
        self.call_count += 1
        i1, j1 = point1
        i2, j2 = point2
        offsets = [(r, c) for r in range(1 + i2 - i1)
                   for c in range(1 + j2 - j1)]
        return {(i1 + r, j1 + c) for r, c in offsets}

    def maximalRectangle(self, matrix) -> int:
        if matrix == []:
            return 0
        rows = len(matrix)
        cols = len(matrix[0])
        indices = [(i, j) for i in range(rows) for j in range(cols)]
        ones = set((i, j) for (i, j) in indices if matrix[i][j] == "1")
        biggest = 0
        for upper_left in indices:
            for bottom_right in indices:
                points = self.areaPoints(upper_left, bottom_right)
                if points <= ones and biggest < len(points):
                    biggest = len(points)
        return biggest


def test_areapoints():
    s = Solution()
    assert s.areaPoints((0, 0), (0, 0)) == {(0, 0)}
    assert s.areaPoints((0, 0), (0, 1)) == {(0, 0), (0, 1)}
    assert s.areaPoints((0, 0), (1, 0)) == {(0, 0), (1, 0)}
    assert s.areaPoints((0, 0), (1, 1)) == {(0, 0), (0, 1), (1, 0), (1, 1)}
    assert s.areaPoints((2, 2), (3, 3)) == {(2, 2), (2, 3), (3, 2), (3, 3)}


def test_areaPointWrongOrder():
    s = Solution()
    assert s.areaPoints((1, 1), (0, 0)) == set()
    assert s.areaPoints((1, 1), (0, 3)) == set()
    assert s.areaPoints((1, 1), (3, 0)) == set()


def test_empty():
    assert Solution().maximalRectangle([]) == 0


def test_small_zero():
    assert Solution().maximalRectangle(["0"]) == 0


def test_small_one():
    assert Solution().maximalRectangle(["1"]) == 1


def test_split():
    matrix = [["1", "0", "1", "0", "0"], ["1", "0", "1", "1", "1"],
              ["1", "1", "1", "1", "1"], ["1", "0", "0", "1", "0"]]
    s = Solution()
    assert s.maximalRectangle(matrix) == 6