Last active
April 10, 2019 13:45
-
-
Save gitschaub/eaedca131827882b4b339966fb157676 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| int **make_dp_mat(int rowSize, int colSize) { | |
| int **dp = (int **)malloc(rowSize * sizeof(int *)); | |
| for(int i = 0; i < rowSize; i++){ | |
| dp[i] = (int *)malloc(colSize * sizeof(int)); | |
| memset(dp[i], 0, colSize * sizeof(int)); | |
| } | |
| return dp; | |
| } | |
| int max_int(int a, int b) { | |
| return a > b ? a : b; | |
| } | |
| // Determine the largest rectangle that can be formed | |
| // from contiguous 1's on a single row | |
| int max_rect_row(int *heights, int len) { | |
| if(len == 0) { | |
| return 0; | |
| } | |
| // For each column and direction (left/right), | |
| // determine the index of the last column with | |
| // height >= the starting column | |
| int dp_left[len]; | |
| int dp_right[len]; | |
| for(int i = 0; i < len; i++) { | |
| int h = heights[i]; | |
| int j = i+1; | |
| for(; j < len; j++) { | |
| if(heights[j] < h) break; | |
| } | |
| dp_right[i] = j; | |
| } | |
| for(int i = len-1; i >= 0; i--) { | |
| int h = heights[i]; | |
| int j = i-1; | |
| for(; j >= 0; j--) { | |
| if(heights[j] < h) break; | |
| } | |
| dp_left[i] = j; | |
| } | |
| int max = 0; | |
| for(int i = 0; i < len; i++) { | |
| int left_dist = i - dp_left[i]; | |
| int right_dist = dp_right[i] - i; | |
| max = max_int(max, heights[i] * (left_dist+right_dist-1)); | |
| } | |
| return max; | |
| } | |
| int maximalRectangle(char** matrix, int matrixRowSize, int *matrixColSizes) { | |
| // Initialize an RxC Rect matrix and set elements to 0 | |
| if(matrixRowSize == 0) return 0; | |
| if((int)matrixColSizes == 0) return 0; | |
| int colSize = (int)matrixColSizes; | |
| int rowSize = matrixRowSize; | |
| int **dp = make_dp_mat(rowSize, colSize); | |
| // For each col in each row, calculate the number | |
| // of contiguous 1's above the column | |
| for(int c = 0; c < colSize; c++) { | |
| dp[0][c] = matrix[0][c] - '0'; | |
| } | |
| for(int r = 1; r < rowSize; r++) { | |
| int p = r-1; | |
| for(int c = 0; c < colSize; c++) { | |
| if(matrix[r][c] == '0') { | |
| dp[r][c] = 0; | |
| continue; | |
| } | |
| dp[r][c] = dp[p][c] + 1; | |
| } | |
| } | |
| int max = 0; | |
| for(int r = 0; r < rowSize; r++) { | |
| max = max_int(max, max_rect_row(dp[r], colSize)); | |
| } | |
| return max; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment