leetcode

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 };