= Solution
Every nonempty axis-aligned <rectangle> has a top-right corner. Enumerate all such corners and retain the greatest area from part (b).
``
var best = 0
var i = 0
while (i < N) {
var j = 0
while (j < N) {
best = math.max(best, maxRectangleAt(i, j))
j += 1
}
i += 1
}
``
The <loop invariant> is that `best` is the greatest area obtained from the corners processed so far, or zero if there are none. Consequently
$$
\boxed{\text{maximum area}=\mathrm{best},\qquad O(N^3)\text{ time},\quad O(N^2)\text{ storage}.}
$$
The preprocessing cost from part (a) is included. An entirely false <matrix>, or an empty one, returns zero. In the printed example, rows $5$ through $9$ and columns $6$ through $8$ give area $5\times3=15$; exhaustive corner enumeration confirms that no larger all-true <rectangle> exists.<Imperative Programming examination paper by the University of Oxford (2014)>[p. 3, example arrays]{ref}
\Image[/past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2014/imperative-programming-2014-maximum-rectangle.png]
{title=An area-15 rectangle and the row run lengths that certify its width}
Back to article page
