The Maximal Rectangle Problem

Given a n*m matrix of 1 and 0, find 1) the max square submatrix of all 1s, 2) the max rectangle matrix of all 1s.

1) is easy, see here. The code here needs a little correction, see here.

2) is hard, see here.