Problem contest with matrix and DP
An $O(n^2)$ algorithm is possible.

Let $A$ be the given matrix.

You compute the side of largest square with the bottom right corner at $(i,j)$, say $S(i,j)$

Now we can compute the side of the larger square for $(i+1, j+1)$ in terms of $S(i,j), S(i+1,j), S(i,j+1)$

as

$$S(i+1,j+1) = \min \{S(i,j), S(i+1,j), S(i,j+1)\} + 1 \quad \text{if}\quad  A[i+1,j+1] = 1$$

and

$$S(i+1,j+1) = 0 \ \text{if }\  A[i+1,j+1] = 0$$

There are other (complicated) $O(n^2)$ algorithms available, which also work for rectangles and can be used for this problem.