#include <assert.h>

// maximalRectangle(rows, cols, matrix) returns the area of the largest
// rectangle containing only 1s in a binary matrix.
int maximalRectangle(int rows, int cols, int matrix[rows][cols]) {
    // keeps track of the height of vertical bars of 1s
    // with the bottom of each bar at the current row
    int heights[101] = {0};

    int maxArea = 0;

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            heights[j] = matrix[i][j] ? heights[j] + 1 : 0;
        }

        // for each right edge, extend left while tracking the shortest bar,
        // which limits the height of the rectangle
        for (int right = 0; right < cols; ++right) {
            int min_height = heights[right];

            for (int left = right; (left >= 0) && (min_height > 0); --left) {
                if (heights[left] < min_height)
                    min_height = heights[left];

                int area = min_height * (right - left + 1);
                maxArea = (area > maxArea) ? area : maxArea;
            }
        }
    }

    return maxArea;
}