Find largest rectangle containing only zeros in an N×N binary matrix

Answer 1

Same question from last year. Use dynamic programming.

Answer 2

there is a very naive algorithm that runs in O(N^6) time. just maintain two indexes in the matrix (O(N^4) time), and determine whether the rectangle defined by them is correct (O(N^2) time).