# 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[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 };
```