The Largest Square of Ones
A grid holds 0s and 1s. Print the AREA of the largest square made entirely
of 1s, or 0 if there is no 1 at all.
Checking every square costs O(r * c * min(r,c)^3) and is hopeless at 300 by
300.
Let side[i][j] be the side of the largest all-ones square whose BOTTOM-RIGHT
corner is at (i, j). Fixing the corner is what makes the recurrence possible:
grid[i][j] == 0 -> side[i][j] = 0
otherwise -> side[i][j] = 1 + min( side[i-1][j],
side[i][j-1],
side[i-1][j-1] )
The min of THREE neighbours is the whole content of the problem, and it is
worth convincing yourself rather than accepting. A square of side k ending
here needs a square of side k-1 ending directly above, one ending directly
left, AND one ending diagonally up-left. Any of the three being smaller caps the
result, and the diagonal one is the neighbour people leave out: without it, an L
shape of ones is mistaken for a filled square.
Filling rows top to bottom and columns left to right means all three neighbours are already final, which is why this is tabulation and not recursion.
The answer is the largest side ANYWHERE in the table, squared, not the bottom-right entry.
Problem 534 builds this exact table and SUMS every entry instead of taking the
maximum, which counts all the all-ones squares of every size rather than
measuring the biggest one. The reason that works is a small proof worth seeing
once you have this table straight: an entry of s means exactly s squares end
at that cell. On the 4 by 5 grid in the first test here, this problem answers 4
and that one answers 15.