# Share my DP solution

• The DP solution proceeds row by row, starting from the first row. Let the maximal rectangle area at row i and column j be computed by [right(i,j) - left(i,j)]*height(i,j).

All the 3 variables left, right, and height can be determined by the information from previous row, and also information from the current row. So it can be regarded as a DP solution. The transition equations are:

left(i,j) = max(left(i-1,j), cur_left), cur_left can be determined from the current row

right(i,j) = min(right(i-1,j), cur_right), cur_right can be determined from the current row

height(i,j) = height(i-1,j) + 1, if matrix[i][j]=='1';

height(i,j) = 0, if matrix[i][j]=='0'

The code is as below. The loops can be combined for speed but I separate them for more clarity of the algorithm.

``````class Solution {public:
int maximalRectangle(vector<vector<char> > &matrix) {
if(matrix.empty()) return 0;
const int m = matrix.size();
const int n = matrix[0].size();
int left[n], right[n], height[n];
fill_n(left,n,0); fill_n(right,n,n); fill_n(height,n,0);
int maxA = 0;
for(int i=0; i<m; i++) {
int cur_left=0, cur_right=n;
for(int j=0; j<n; j++) { // compute height (can do this from either side)
if(matrix[i][j]=='1') height[j]++;
else height[j]=0;
}
for(int j=0; j<n; j++) { // compute left (from left to right)
if(matrix[i][j]=='1') left[j]=max(left[j],cur_left);
else {left[j]=0; cur_left=j+1;}
}
// compute right (from right to left)
for(int j=n-1; j>=0; j--) {
if(matrix[i][j]=='1') right[j]=min(right[j],cur_right);
else {right[j]=n; cur_right=j;}
}
// compute the area of rectangle (can do this from either side)
for(int j=0; j<n; j++)
maxA = max(maxA,(right[j]-left[j])*height[j]);
}
return maxA;
}
``````

};

If you think this algorithm is not easy to understand, you can try this example:

``````0 0 0 1 0 0 0
0 0 1 1 1 0 0
0 1 1 1 1 1 0
``````

The vector "left" and "right" from row 0 to row 2 are as follows

row 0:

``````l: 0 0 0 3 0 0 0
r: 7 7 7 4 7 7 7
``````

row 1:

``````l: 0 0 2 3 2 0 0
r: 7 7 5 4 5 7 7
``````

row 2:

``````l: 0 1 2 3 2 1 0
r: 7 6 5 4 5 6 7
``````

The vector "left" is computing the left boundary. Take (i,j)=(1,3) for example. On current row 1, the left boundary is at j=2. However, because matrix[1][3] is 1, you need to consider the left boundary on previous row as well, which is 3. So the real left boundary at (1,3) is 3.

I hope this additional explanation makes things clearer.

• This dp way is even more elegant than the stack solution!

• Nice solution, thanks for your sharing. But for right(i,j), it should be min(right(i-1,j), curright). You got it right in the code but a typo in the transition equations.

• Thanks for pointing out. The typo is fixed.

• This solution is so clever that I think so hard to understand it.
`height` counts the number of successive '1's above (plus the current one). The value of `left` & `right` means the boundaries of the rectangle which contains the current point with a height of value `height`.

• Brilliant solution!

• This post is deleted!

• Beautiful method!!

• U r a genius really!!!!!!!

• like this solution.

• really brilliant method!!!!

• Really amazing solution!!!

• Awesome, guy!

• Incredible method！

• Salute Bro..

• Very neat solution. I rewrote it in C# by modifying them to a 2-d DP array

``````public int MaximalRectangle(char[,] matrix) {
int n = matrix.GetLength(1), maxA = 0;
int[,] dp = new int[n, 3]; //[i, 0] is left; [i, 1] is right; [i, 2] is height
for(int i = 0; i < n; i++) dp[i, 1] = n;
for(int i = 0; i < matrix.GetLength(0); i++) {
int cur_left = 0, cur_right = n;
for(int j = 0; j < n; j++) {
if(matrix[i, j] == '1')     // compute height (can do this from either side)
dp[j, 2]++;
else dp[j, 2]=0;
if(matrix[i, j] == '1')     // compute left (from left to right)
dp[j, 0] = Math.Max(dp[j, 0], cur_left);
else { dp[j, 0] = 0; cur_left = j + 1; }
}
// compute right (from right to left)
for(int j = n - 1; j >= 0; j--) {
if(matrix[i, j] == '1') dp[j, 1] = Math.Min(dp[j, 1], cur_right);
else { dp[j, 1] = n; cur_right = j; }
}
// compute the area of rectangle (can do this from either side)
for(int j = 0; j < n; j++)
maxA = Math.Max(maxA, (dp[j, 1] - dp[j, 0]) * dp[j, 2]);
}
return maxA;
}``````

• cool~!! 相当漂亮的DP！！

• I modified the boundary for the right side to make both direction consistent and confirmed to definition

``````if(matrix.empty()) return 0;
const int m = matrix.size();
const int n = matrix[0].size();
int left[n], right[n], height[n];
fill_n(left,n,0); fill_n(right,n,n); fill_n(height,n,0);
int maxA = 0;
for(int i=0; i<m; i++) {
int cur_left=0, cur_right=n-1;
for(int j=0; j<n; j++) { // compute height (can do this from either side)
if(matrix[i][j]=='1') height[j]++;
else height[j]=0;
}
for(int j=0; j<n; j++) { // compute left (from left to right)
if(matrix[i][j]=='1') left[j]=max(left[j],cur_left);
else {left[j]=0; cur_left=j+1;}
}
// compute right (from right to left)
for(int j=n-1; j>=0; j--) {
if(matrix[i][j]=='1') right[j]=min(right[j],cur_right);
else {right[j]=n-1; cur_right=j-1;}
}
// compute the area of rectangle (can do this from either side)
for(int j=0; j<n; j++)
maxA = max(maxA,(right[j]-left[j]+1)*height[j]);
}
return maxA;``````

• This post is deleted!

• Great code! I guess it would be easier to understand by also visualizing `height` for the above example :-)

``````0th row: 0 0 0 1 0 0 0
height: 0 0 0 1 0 0 0
left: 0 0 0 3 0 0 0
right 7 7 7 4 7 7 7

1st row: 0 0 1 1 1 0 0
height: 0 0 1 2 1 0 0
left: 0 0 2 3 2 0 0
right: 7 7 5 4 5 7 7

2nd row: 0 1 1 1 1 1 0
height: 0 1 2 3 2 1 0
left: 0 1 2 3 2 1 0
right: 7 6 5 4 5 6 7
``````

Very nice to see the heights accumulate in `height` and the values of `left` and `right` updating in the loop.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.