# 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.Using`dp[i][j]` record the continous '1' in row`i` 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 row`k` before `i` and get the minmal length during`dp[i][j]`and`dp[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.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 };``````