leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0085.cpp (766B)

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