leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0085.cpp (766B)

0 class Solution { 1 public: 2 int maximalRectangle(const vector<vector<char>> &matrix) const { 3 const int n = size(matrix), m = size(matrix[0]); 4 static int dp[202][202] = {0}; 5 int res = 0; 6 7 for (int i = n - 1; i >= 0; i--) { 8 dp[i][m] = 0; 9 for (int j = m - 1, acc = 0; j >= 0; j--) { 10 dp[i][j] = matrix[i][j] == '1' ? dp[i][j + 1] + 1 : 0; 11 } 12 } 13 14 for (int i = 0; i < n; i++) { 15 for (int j = 0; j < m; j++) { 16 for (int l = i, len = m; l < n && matrix[l][j] == '1'; l++) { 17 len = min(len, dp[l][j]); 18 res = max(res, (l - i + 1) * len); 19 } 20 } 21 } 22 23 return res; 24 } 25 };