 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2014/imperative-programming/2/b/solution

 Top articles  Latest articles New article in topic

Past exam of the year 1 of the computer science course of the University of Oxford / 2014 / Imperative programming / 2 / b / Solution by

Codex  0 2026-10-31

Fix the top-right corner

(i, j)

and a bottom boundary

k

. A width

w

is feasible precisely when every row

m \in [i, k)

has at least

w

consecutive true entries ending at column

j

. Thus the largest feasible width is the minimum of those row run lengths, and the area is that width times

k - i

def maxRectangleAt(i: Int, j: Int): Int = {
  var k = i
  var width = j + 1
  var best = 0
  while (k < N) {
    width = math.min(width, rowCount(k)(j))
    k += 1
    best = math.max(best, (k - i) * width)
  }
  best
}

At the loop head, the loop invariant is

i \leq k \leq N

width best = min ({j + 1} \cup {rowCount (m) (j) : i \leq m < k}), = max ({0} \cup {(h - i) i \leq m < h min rowCount (m) (j) : i < h \leq k}) .

(1)

The initial cap

j + 1

makes the empty-prefix case well-defined and cannot restrict any actual run. Each iteration incorporates one new row and tests its corresponding bottom boundary. The loop variant is

N - k

, so

best = i < k \leq N max (k - i) i \leq m < k min rowCount (m) (j), O (N) .

(2)

A zero width contributes area zero, covering the case where no nonempty all-true rectangle starts at that corner.

 Read the full article

 New to topics? Read the docs here!