This took me a while to figure out when I tried this for the first time. I had to understand and code up https://leetcode.com/problems/largest-rectangle-in-histogram/ (thanks to other comments in the discussion forum!) before I attempted this one again.

The idea is each time you iterate through a row in input matrix, keep track of the heights in a separate array (which is your histogram input). After you go through a row, calculate the maximum area for that histogram and compare it with current maximum and update it if necessary.

```
For example:
1 1 0 1
0 0 1 0
After iterating though row 1, your histogram = [1 1 0 1], current Area = 2 and so maxArea = 2
After iterating though row 2, your histogram = [0 0 1 0], current Area = 1 and so maxArea = 2
// O(n)
private int getMaxRectangleArea(int[] heights) {
int maxArea = 0;
Stack<int> rectHeights = new Stack<int>();
int current = 0;
while(current < heights.Length) {
if (rectHeights.Count == 0 || heights[rectHeights.Peek()] <= heights[current]) {
rectHeights.Push(current++);
} else {
int currHeightIndex = rectHeights.Pop();
int areaWithTop = heights[currHeightIndex] *
(rectHeights.Count == 0 ? current : current - 1 - rectHeights.Peek());
maxArea = Math.Max(maxArea, areaWithTop);
}
}
while (rectHeights.Count > 0) {
int currHeightIndex = rectHeights.Pop();
int areaWithTop = heights[currHeightIndex] * (rectHeights.Count == 0 ? current : current - 1 - rectHeights.Peek());
maxArea = Math.Max(maxArea, areaWithTop);
}
return maxArea;
}
// O(n ^ 2)
public int MaximalRectangle(char[,] matrix) {
int[] heights = new int[matrix.GetLength(1)];
int maxArea = 0;
for(int row = 0; row < matrix.GetLength(0); row++) {
for(int column = 0; column < matrix.GetLength(1); column++) {
if (matrix[row, column] == '1') {
heights[column]++;
} else if (matrix[row, column] == '0') {
heights[column] = 0;
}
}
maxArea = Math.Max(maxArea, getMaxRectangleArea(heights));
}
return maxArea;
}
```