#include <iostream>
#include <vector>
#include <stack>
// Function to compute largest rectangle area in a histogram
int largestRectangleArea(const std::vector<int>& heights) {
std::stack<int> st;
int maxArea = 0;
int n = heights.size();
for (int i = 0; i <= n; i++) {
int h = (i == n) ? 0 : heights[i];
while (!st.empty() && h < heights[st.top()]) {
int height = heights[st.top()];
st.pop();
int width = st.empty() ? i : i - st.top() - 1;
maxArea = std::max(maxArea, height * width);
}
st.push(i);
}
return maxArea;
}
// Main function to compute maximal rectangle in binary matrix
int maximalRectangle(const std::vector<std::vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
int rows = matrix.size();
int cols = matrix[0].size();
std::vector<int> heights(cols, 0);
int maxArea = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
// Update histogram heights
if (matrix[r][c] == '1') {
heights[c] += 1;
} else {
heights[c] = 0;
}
}
// Compute largest rectangle for this histogram
maxArea = std::max(maxArea, largestRectangleArea(heights));
}
return maxArea;
}
int main() {
try {
// Define the matrix
std::vector<std::vector<char>> matrix = {
{'1','0','1','0','0'},
{'1','0','1','1','1'},
{'1','1','1','1','1'},
{'1','0','0','1','0'}
};
int result = maximalRectangle(matrix);
std::cout << "Largest rectangle area of 1's: " << result;
} catch (const std::exception& e) {
std::cerr << "Error: " << e.what();
return 1;
}
}
/*
run:
Largest rectangle area of 1's: 6
*/
