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
} Articles by others on the same topic
There are currently no matching articles.