Maximum all-true rectangle

In a Boolean matrix, find an axis-aligned rectangle containing only true entries and having maximum area. One approach first records each row's consecutive true run ending at each column. For each possible top-right corner, extend downwards, maintaining the minimum run width and maximizing height times width. This uses $O(N^3)$ time complexity on an $N$ by $N$ matrix after $O(N^2)$ preprocessing.

The number of consecutive true entries ending at a specified column of one row of a Boolean matrix. It is zero at a false entry and otherwise one plus the previous column's row run length, taking the value before column zero to be zero.