Find a maximal rectangle of 1s Background

I want to buy an plot of land and build my house on it.
My house should be rectangular, and as large as possible; however, the available plots have lots of rocky areas that I cannot build on, and I'm having trouble fitting a potential house on the plots.
I want you to write a program that analyzes the plots for me.

Input and output

Your input is a rectangular 2D array of bits, of size at least 1&times;1, in any reasonable format.
The array represents a plot of land; 1s are "good" areas where I could build my house, and 0s are "rocky" areas where the house cannot be built.

Your output shall be the maximal area of a solid rectangle of 1s in the input array.
It represents the area of the largest house I could build on the plot.
Note that if there are no 1s in the input, then the output is 0.

Example

Consider the input

101
011
111


The largest rectangle of 1s is the 2&times;2 rectangle in the lower right corner.
This means that the correct output is 4.

Rules and scoring

You can write a full program or a function.
The lowest byte count wins, and standard loopholes are disallowed.

Test cases

0
-&gt; 0

1
-&gt; 1

00
00
-&gt; 0

01
10
-&gt; 1

01
11
-&gt; 2

111
010
111
-&gt; 3

101
011
111
-&gt; 4

0111
1110
1100
-&gt; 4

1111111
1110111
1011101
-&gt; 7

111011000
110111100
001111110
011111111
001111110
000111100
000011000
-&gt; 20

000110000
110110010
110111110
110011100
010011111
111111111
111101110
-&gt; 12
Jelly, 21 20 18 17 bytes

ṡṂ€€×"
‘×¥\ç"Ụ€FṀ


Try it online! or verify all test cases.

Background

Let M be a matrix of bits such as

0 0 0 1 1 0 0 0 0
1 1 0 1 1 0 0 1 0
1 1 0 1 1 1 1 1 0
1 1 0 0 1 1 1 0 0
0 1 0 0 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1 0


We start by counting the number of 1 bits in each column of M, resetting the count every time we encounter a 0 bit.

For our example matrix, this gives

0 0 0 1 1 0 0 0 0
1 1 0 2 2 0 0 1 0
2 2 0 3 3 1 1 2 0
3 3 0 0 4 2 2 0 0
0 4 0 0 5 3 3 1 1
1 5 1 1 6 4 4 2 2
2 6 2 2 0 5 5 3 0


Next, we compute all contiguous sublists of each row. We achieve this by generating all slices of length k, where k varies between 1 and the number of entries in each row.

For the penultimate row, this gives

[1], [5], [1], [1], [6], [4], [4], [2], [2]
[1, 5], [5, 1], [1, 1], [1, 6], [6, 4], [4, 4], [4, 2], [2, 2]
[1, 5, 1], [5, 1, 1], [1, 1, 6], [1, 6, 4], [6, 4, 4], [4, 4, 2], [4, 2, 2]
[1, 5, 1, 1], [5, 1, 1, 6], [1, 1, 6, 4], [1, 6, 4, 4], [6, 4, 4, 2], [4, 4, 2, 2]
[1, 5, 1, 1, 6], [5, 1, 1, 6, 4], [1, 1, 6, 4, 4], [1, 6, 4, 4, 2], [6, 4, 4, 2, 2]
[1, 5, 1, 1, 6, 4], [5, 1, 1, 6, 4, 4], [1, 1, 6, 4, 4, 2], [1, 6, 4, 4, 2, 2]
[1, 5, 1, 1, 6, 4, 4], [5, 1, 1, 6, 4, 4, 2], [1, 1, 6, 4, 4, 2, 2]
[1, 5, 1, 1, 6, 4, 4, 2], [5, 1, 1, 6, 4, 4, 2, 2]
[1, 5, 1, 1, 6, 4, 4, 2, 2]


Next, we map each slice to the product of its minimum and its length. For each slice, this computes the area of the rectangle of 1 bits of maximum height that has the given slice as bottom row.

For the slices of length 3 of the penultimate row of our example matrix, this gives

3 3 3 3 12 6 6


All that's left to do is take the maximum across all slices of all rows.

For our example matrix, this gives 12.

How it works

‘×¥\ç"Ụ€FṀ  Main link. Argument: M (2D list of bits)

   \        Reduce the columns of M by the link to the left.
  ¥           Combine the two atoms to the left into a dyadic chain.
‘               Increment the left argument.
 ×              Multiply the result with the right argument.
      Ụ€    Grade up each; yield the indices of each row of M, sorted by their
            values. The order is not important here; we just need the indices.
    ç"      Apply the helper link to each element of the result to the left and
            the corresponding element of the result to the right.
        F   Flatten the resulting, nested list.
         Ṁ  Extract the maximum.


ṡṂ€€×"      Helper link. Arguments: R (row), X (indices of R)

ṡ           For each k in X, split R into overlapping slices of length k.
 Ṁ€€        Compute the minimum of each individual slice.
    ×"      Multiply the minima of all slices of length k by k.