#include <stdbool.h>

int maximalRectangle(int m, int n, int matrix[m][n]){
    int max_area = 0;   //represent max area of rectangle.
    for (int row = 0; row < m; row++){

        for (int col = 0; col < n; col++){

            //Let entry with value 1 as the 
            //left-up corner of the rectangle.
            if (matrix[row][col] == 1){

                //Boolean value to show if there 
                //are more rectangles in this entry.
                bool has_rec = true;

                //The row index of left-down corner of the rectangle.
                int row_expand = row;

                //The column index of right-up corner of the rectangle.
                int col_expand = col;

                //This value represent the maximum
                //col_expand value under certain row_expand value.
                //Set to n - 1 for now, which is the maximum column index.
                int rightmost = n - 1;


                //iterating every possible maximum rectangle area.
                while (has_rec){

                    col_expand = col;   //Initialize col_expand value.

                    /*
                        Find maximum column index under current row_expand:
                        1. Current columm is at the edge of the matrix.
                        2. Current column reaches rightmost value.
                        3. Next entry is zero entry.
                        Boundry check is before entry check so there's no
                        boundry errors.
                    */
                    while (
                    col_expand < n - 1
                    && col_expand < rightmost
                    && matrix[row_expand][col_expand + 1] != 0
                    )
                        col_expand++;

                    //Make sure further rectangles with larger 
                    //row_expand value don't contain the invalid entry.
                    rightmost = col_expand;

                    //Calculate area of the rectangle.
                    //The length and width should be one more than
                    //the difference of indexes.
                    int length = col_expand - col + 1;
                    int width = row_expand - row + 1;
                    int area = length * width;

                    //Compare with previous max area and update.
                    if (area > max_area)
                        max_area = area;
                            
                    //Check if current row is at the edge,
                    //or there's a zero entry beneath.
                    if (row_expand >= m - 1 
                    || matrix[row_expand + 1][col] == 0)

                        has_rec = false;

                    else
                        //Procede to the next row.
                        row_expand++;
                }
            }

        }

    }

    //Return maximum area.
    return max_area;
}