Max submatrix problem

Given a binary matrix M of 0s and 1s.
1) find the maximal square sub-matrix.
2) find the maximal sub-matrix.

1) is easy. The key is to setup a helper matrix H, whose first top row and first left column are the same as the original matrix, and other cells are obtained by:
if (M[i][j] == 1) H[i][j] = min(M[i-1][j], M[i][j-1], M[i-1][j-1]) + 1;
else H[i][j] = 0;
The H[i][j] is the size of the maximal square sub-matrix using H[i][j] as right bottom cell. See here for details. It's dynamic programming, time cost is O(n*m).

2) is harder. But it can be solved using the Max rectangle problem. First we pre-process matrix M, so each cell's value is the number of consecutive ones to the right on the same row. Now we can start scanning the matrix M from the left most column to the right most column, treating each column as the input of a max rectangle problem. Time complexity is O(mn), space complexity is O(n) for the stack used, where n is number of rows, m is number of columns. See here for reference.

There are variation problems of this type. For example:
3) Given binary square matrix, find the max square sub-matrix such that its borders are all 0s. See here for the question. As for solution, we may try to apply 1) to find the max sub-matrix of all 1s, and then corresponding max square sub-matrix with 0s on borders, but then it's possible the corner is 1. Therefore applying 1) directly is not a complete answer.

4) Given a matrix of positive and negative numbers, find the sub-matrix with the maximal sum. (Kadane's 2D problem). Solution is: for each cell of each row, get the sum of each prefix (m*(m-1)/2 possibilities). Then for each column, apply the Kadane 1D solution. Get the max of all kadane 1D solutions. This is O(m^2 * n), or O(n^3) if m == n.

See here for a reference discussion of these problems.