maximal rectangle

maximal rectangle

Typical 2d dynamic programing

When we meet such a question like this. We could think the problem like this.

How could we resolve this problem if it is a line.

This is easy, using dp[i] to record the maximal continous number of '1'. If char in i then dp[i] = dp[i-1]+1. Otherwise, dp[i] = 0. Then we find the maximal value in dp.

When this problem comes in matrix

It is not a hard question too.Usingdp[i][j] record the continous '1' in rowi before j. So we get the answer by rows. Supposing that we get dp[i][j]. Now we need to check the rows before i to find the bigest matrix filled with '1' and the char in [j] must be '1'. So, we check rowk before i and get the minmal length duringdp[i][j]anddp[k][j]. Then multiply the rows, we get each size of matrixs like this and we record the maximal value as result.

 1 class Solution {
 2 public:
 3     int maximalRectangle(vector<vector<char> > &matrix) {
 4         int n = matrix.size();
 5         if ( !n ) {
 6             return 0;
 7         }
 8         int m = matrix[0].size();
 9         if ( !m ) {
10             return 0;
11         }
12         int dp[n][m];
13         int result = 0;
14         memset(dp,0,sizeof(dp));
15         for ( int i = 0; i < n; i++ ) {
16             for ( int j = 0; j < m; j++ ) {
17                 if ( '1' == matrix[i][j] ) {
18                     if ( j > 0 ) {
19                         dp[i][j] = dp[i][j-1]+1;
20                     } else {
21                         dp[i][j] = 1;
22                     }
23                     result = max(result,dp[i][j]);
24                     int r = dp[i][j];
25                     for ( int k = i-1; k >= 0 && dp[k][j]; k-- ) {
26                             r = min(r,dp[k][j]);
27                             result = max(result,r*(i-k+1));
28                     }
29                 }
30             }
31         }
32         return result;
33     }
34 };

Loading Disqus comments...
Table of Contents