Problem:
A binary matrix is a matrix each of whose elements is either 0 or 1. Matrix A is said to be larger than matrix B if A has more entries than B. Given a binary matrix, the objective here is to find out the largest rectangle (submatrix) with elements being all 1’s.
Example: in above matrix, the largest all 1’s rectangle has 9 elements.
Problem solving
Suppose the matrix has m rows and n columns. The following will discuss an efficient algorithm which has time complexity O(mn). To begin with, we show some properties of all 1’s largest rectangle.
Definition
 Bar: A bar is a line of matrix elements being all 1’s. Bar could be horizontal or vertical according to its orientation.
 Histogram: A histogram is one horizontal bar being the base concatenating with a number of vertical bars (‘base’ means that the bottoms of vertical bars are located on the horizontal bar). We call a histogram basek histogram if its base horizontal bar is at kth row. Moreover, if a histogram cannot be contained within any other histogram except itself, it is a maximal histogram.
Example: maximal histograms in a matrix
Theorem 1: The largest rectangle is contained within a maximal histogram.
Proof. Note that the largest rectangle itself is a histogram. So it must be contained within some maximal histogram.
Theorem 2: For each k, any two basek maximal histograms do not intersect.
Proof. This could be proved by contradiction. Assume that two basek maximal histograms do intersect. Then they could be combined into a larger histogram which contains the previous two. This contradicts with the maximal property.
Theorem 2 implies that the maximal histograms could be effectively enumerated. Then by finding out the largest rectangle within each maximal histogram, we could have the overall largest rectangle.
Algorithm
A natural greedy strategy is to incrementally grow the subset by try putting in compatible activities. To use this strategy, the activities should have an order so that they can be tried one by one. Interestingly, an increasing order of finish times will lead to optimal solution (while other orderings, such as ordering in start times, will not). The algorithm is presented as follows.
LargestRectangle
For each row k
For each basek histogram H
R = Largestrectangleinhistogram(H)
If size(R) > size(maxRectangle)
maxRectangle = R
Return maxRectangle

The rest is to find out the largest rectangle in a given histogram. To do this, we sweep from the histogram’s left to right and maintain a stack S: Let height(i) be the height of ith vertical bar (for boundary case let height(0) = 0 and height(n+1) = 0, where n is the number of bars in the histogram). In ith iteration of the sweeping we pop out all entries in S that have less height than height(i), and then push i into S, as following figure illustrates.
Fact 3: The heights of bars in S are nondecreasing.
Define prev(i) as the element before i when element i is in stack S (there must be only one such element for each i). Then
Fact 4: height(j) > height(i) for any prev(i) < j < i.
The following theorem will finally lead to our Largestrectangleinhistogram algorithm.
Theorem 5: If kth bar contains the right border of the largest rectangle, then (i) height(k+1) < height(k); ( ii ) size of largest rectangle = max{ (kprev(j)) * height(j) }, where j is each element in stack S at the start of iteration (k+1) such that height( j ) > height( k+1 ).
Proof. It is easy to see property (i), otherwise we could extend the rectangle so that it contains the (k+1)th bar, which forms a contradiction to the right border precondition. To prove (ii), first note that the largest rectangle must contain some whole bar j (otherwise we could expand the rectangle upwards). If j is not an element in S at the start of (k+1)th iteration, then there exists an element j ' in S such that j < j ' and height(j) > height( j ' ). In this situation j cannot be contained within a rectangle (with kth bar as right border). And for each j in S, observe that height( i ) >= height( j ) for any prev( j ) < j <= k and height(prev( j )) < height( j ). So the largest possible rectangle containing bar j has size (kprev(j))*height(j). Thus by enumerating j’s in S we will find out the largest rectangle in the histogram. Moreover, we will not consider j’s in S such that height(j) <= height(k+1) (i.e. j <= prev(k+1)) for similar border argument as case ( i ).
Algorithm
Largestrectangleinhistogram
S = { 0 }
maxSize = 0
maxRectangle = null
For k = 1 to n+1
j = top element in S
While height(k) < height(j) do
Pop out the top element in S
prev_j = top element in S
newSize = ( k – 1 – prev_j ) * height(j)
If newSize > maxSize
maxSize = newSize
update maxRectangle
j = prev_j
Push k into S
(We set height(0) = height(n+1) = 0 for boundary condition) 
Time Complexity:
To implement Largestrectangle, an auxiliary matrix will be prepared for quick retrieval of bar height in each maximal histogram, so the height() query only takes O(1) time. Sweeping through a histogram of length L takes O(L) amortized time considering the stack operation. The total length of every possible maximal histogram will not exceed m*n, which is the size of matrix. So the total time complexity is O(mn).
Space Complexity:
In implementation of the algorithm an auxiliary matrix of size m*n will be created. Sweeping through a histogram requires a stack of size n, which could be reused for each histogram. So the total space complexity is dominated by the auxiliary matrix and it is O(mn).
Pseudo Code
Largestrectangle
Input: a matrix matr[1..m][1..n] valued 0 or 1.
Output: four integers (x^{0}, y^{0}, x^{0}, y^{0}) denoting the lefttop
and rightbottom corner coordinates of the largest all 1's submatrix
for i = 1 to m
height[i][0] = 0
height[i][n+1] = 0
for j = 1 to n
height[1][i] = matr[1][j]
for i = 2 to m
for j = 1 to n
if matr[i][j] == 0
height[i][j] = 0
else
height[i][j] = height[i1][j] + matr[i][j]
maxSize = 0
maxRectangle = null
for i =1 to m
S = { 0 }
for k = 1 to n+1
j = top(S)
while height(k) < height(j)
pop(S)
prev_j = top(S)
newSize = ( k – 1 – prev_j ) * height[i][j]
if newSize > maxSize
maxSize = newSize
maxRectangle = ( iheight[i][j]+1, prev_j+1, i, k1 )
j = prev_j
push(S, k)
return maxRectangle

