[Leetcode] Maximal Rectangle

Problem 

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

Algorithm 

Build a 2D matrix H, where H[i][j] indicates the max number of continuous "1" above (including) matrix element (i,j).  

                                     H[i][j]  =  0                          if A[i][j] = 0

                                                      H[i-1][j] + 1       else. 

After building the H matrix, we can compute the Max Rectangle in Histogram using each row as the base. Since for each row, the Max Rectangle in Histogram needs O(n) time,  the total running time is O(n^2). 

Code