This link shares a nice solution with explanation using DP. You will be clear of the algorithm after running it on its suggested example:
matrix = [ [0, 0, 0, 1, 0, 0, 0], [0, 0, 1, 1, 1, 0, 0], [0, 1, 1, 1, 1, 1, 0]];
The code is rewritten as follows.
1 class Solution { 2 public: 3 int maximalRectangle(vector<vector<char>>& matrix) { 4 if (matrix.empty()) return 0; 5 const int m = matrix.size(), n = matrix[0].size(); 6 int *left = new int[n](), *right = new int[n](), *height = new int[n](); 7 fill_n(right, n, n); 8 int area = 0; 9 for (int i = 0; i < m; i++) { 10 int l = 0, r = n; 11 for (int j = 0; j < n; j++) 12 height[j] += matrix[i][j] == '1' ? 1 : -height[j]; 13 for (int j = 0; j < n; j++) { 14 if (matrix[i][j] == '1') left[j] = max(left[j], l); 15 else left[j] = 0, l = j + 1; 16 } 17 for (int j = n - 1; j >= 0; j--) { 18 if (matrix[i][j] == '1') right[j] = min(right[j], r); 19 else right[j] = n, r = j; 20 } 21 for (int j = 0; j < n; j++) 22 area = max(area, (right[j] - left[j]) * height[j]); 23 } 24 return area; 25 } 26 };
