# Accepted 12ms DP solution in c++, similar with what is used in Maximal Rectangle.

• This is a DP solution in c++, 12ms, similar with what is used in Maximal Rectangle. Here is the general idea of this solution, it is presented by morrischen2008, thanks for his outstanding work.

``````class Solution {
public:
int maximalSquare(std::vector<std::vector<char> > &matrix) {
if(matrix.empty())
return 0;
int rows = matrix.size(), cols = matrix[0].size(), length = 0;
std::vector<int> left(cols), right(cols, cols), height(cols);
for(int i = 0; i != rows; ++i) {
int cur_left = 0, cur_right = cols;
for(int j = cols - 1; j >= 0; --j)
if(matrix[i][j] == '1')
right[j] = std::min(right[j], cur_right);
else {
right[j] = cols;
cur_right = j;
}
for(int j = 0; j != cols; ++j)
if (matrix[i][j] == '1') {
left[j] = std::max(left[j], cur_left);
++height[j];
length = std::max(length, std::min(right[j] - left[j], height[j]));
}
else {
left[j] = height[j] = 0;
cur_left = j + 1;
}
}
return length * length;
}
};
``````

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