Revisiting an old problem

A while ago, I asked if there was an O(n^2) solution to the following problem:

Given a rectangular matrix of only 1s or 0s, find the largest contiguous rectangle (or square) with edges parallel to the sides of the original rectangular matrix such that this rectangle contains all 1s.

After revisiting the problem today, I believe I have thought of such a solution.

Ask me if you want it :)