 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2014/imperative-programming/2/c/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

maximum area = best, O (N^{3}) time, O (N^{2}) 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 \times 3 = 15

; exhaustive corner enumeration confirms that no larger all-true rectangle exists.^[ref]

 New to topics? Read the docs here!