# My DP solution using C++

• In my code, the `flag` contains the numbers of the largest lists containing only 1's in the right and the top of `matrix[i][j]`, and that is first and second variables of `pair<int, int>` in code.Then i decide to find the largest rectangle that contains `matrix[i][j]` in lower right corner .

``````class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
int m = matrix.size(), n = matrix[0].size();
vector<vector<pair<int, int>>> flag(m, vector<pair<int, int>>(n));
int maxRct = 0;
for (int i = 0; i<m; i++)
{
for (int j = 0; j<n; j++)
{
if (matrix[i][j] == '0')
flag[i][j].second = flag[i][j].first = 0;
else
{
flag[i][j].first = j == 0 ? 1 : flag[i][j-1].first + 1;
flag[i][j].second = i == 0 ? 1 : flag[i-1][j].second + 1;
int first = flag[i][j].first;
for (int m = i; m >= 0 && flag[m][j].first > 0; m--)
{
first = min(first, flag[m][j].first);
maxRct = max(maxRct, first*(i-m+1));
}
}
}
}
return maxRct;
}
};
``````

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