For each row, keep the row run length of the processed prefix. A false entry resets the length to zero; a true entry extends it by one.The outer loop invariant states that rows before
val rowCount = Array.ofDim[Int](N, N)
var i = 0
while (i < N) {
var j = 0
var run = 0
while (j < N) {
if (a(i)(j)) run += 1 else run = 0
rowCount(i)(j) = run
j += 1
}
i += 1
}i have all their correct row run lengths. The inner loop invariant states that columns before j in row i are correct and that run is the length of the all-true suffix of a(i)[0..j). Initially this suffix is empty. Updating run gives exactly the suffix length ending at column j, proving the required formula, including zero at a false entry. Every cell is visited once:where the fictitious value at column is zero. The table itself uses storage.Fix the top-right corner and a bottom boundary . A width is feasible precisely when every row has at least consecutive true entries ending at column . Thus the largest feasible width is the minimum of those row run lengths, and the area is that width times .At the loop head, the loop invariant is ,The initial cap 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 , soA zero width contributes area zero, covering the case where no nonempty all-true rectangle starts at that corner.
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
}Every nonempty axis-aligned rectangle has a top-right corner. Enumerate all such corners and retain the greatest area from part (b).The loop invariant is that
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
}best is the greatest area obtained from the corners processed so far, or zero if there are none. ConsequentlyThe preprocessing cost from part (a) is included. An entirely false matrix, or an empty one, returns zero. In the printed example, rows through and columns through give area ; exhaustive corner enumeration confirms that no larger all-true rectangle exists.[ref]
Articles by others on the same topic
There are currently no matching articles.