#include <stdio.h>
#include <assert.h>

int maximalRectangle(int m, int n, int matrix[m][n]) {
    int current_maximum = 0;
    // Loop throughout the entire matrix
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 1) {
                //printf("found a 1 at %d, %d\n", i, j);
                // Plan is, go row by row, and "trim" down until we find all possible rectangles
                // So first, loop the initial row
                int rowlength = 1;
                for (int k = j + 1; k < n; k++) {
                    if (matrix[i][k] == 1) {
                        rowlength++;
                    }
                    else {
                        break;
                    }
                }
                //printf("First row length is %d\n", rowlength);
                // Now check all possible row lengths to compare largest area:
                for (int current_row_length = rowlength; current_row_length > 0; current_row_length--) {
                    //printf("computing area with row length %d\n", current_row_length);
                    int rectangle_height = 1;
                    // now, loop subsequent rows
                    int current_row = i + 1;
                    while (current_row < m) {
                        // row_length_counter checks if the subsequent row is just as long
                        int row_length_counter = 0;
                        for (int k = j; k <= j + current_row_length - 1; k++) {
                            if (matrix[current_row][k] == 1) {
                                row_length_counter++;
                            }
                            else {
                                break;
                            }
                        }
                        if (row_length_counter != current_row_length) {
                            break;
                        }
                        current_row++;
                        rectangle_height++;
                    }
                    // now the rectangle should have area rowlength * rectangle_height
                    //printf("found a rectangle with size %d %d area %d\n", current_row_length, rectangle_height, current_row_length * rectangle_height);
                    if (current_maximum < current_row_length * rectangle_height) {
                        current_maximum = current_row_length * rectangle_height;
                        //printf("New maximum %d\n", current_maximum);
                    }
                }
            }
        }
    }
    // finally, after checking every potential rectangle, return max
    //printf("max: %d\n", current_maximum);
    return current_maximum;
}