PasteBins

New Paste Browse

#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;
}

Paste Settings

Paste Title : [Optional]

Paste Folder : [Optional]

Syntax Highlighting : [Optional]

Paste Expiration : [Optional]

Paste Status : [Optional]

Password : [Optional]

Description: [Optional]

Tags: [Optional]

Encrypt Paste (?)

You are currently not logged in, this means you can not edit or delete anything you paste. Sign Up or Login

Recent Pastes

VIDEO С.P T33n
Plaintext | 2 | 6 minutes ago
LEAKS 11-17 MEGA T33n
Plaintext | 4 | 26 minutes ago
A4Q3-1
C-like | 3 | 40 minutes ago
DATA BASES LINKEDIN LINKEDIN INSTAGRAM INVESTORS VISA REDLINE LOG HACK
Plaintext | 4 | 54 minutes ago
A4Q1-3
C-like | 16 | 1 hour ago
T33n MEGA LEAKS
Plaintext | 23 | 1 hour ago
A4Q1-2
Plaintext | 19 | 1 hour ago

Paste Settings

Site Languages