# My accepted code. Is it O(n^3) solution?

• The idea is that: first calculate the consecutive '1's per row until the target position. Therefore:
dp[i][j] = k when there are k consecutive '1's from dp[i][j-k+1] to dp[i][j]
Then, for each (i,j), dp[i][j] means the bottom edge of the rectangle, and then look up, to add each possible dp[k][j](k = 0...i-1), and compare with the max.

Here is the code:

``````public class Solution {
public int maximalRectangle(char[][] matrix) {
if (matrix == null || matrix.length == 0)
return 0;

int row = matrix.length;
int col = matrix[0].length;
int max = 0;

int[][] dp = new int[row][col];

// initialize dp to have dp[i][j] = k when there are k consecutive '1's from dp[i][j-k+1] to dp[i][j]

for (int i = 0; i < row; i++){
if (matrix[i][0] == '1')
dp[i][0] = 1;
}

for (int i = 0; i < row; i++){
for (int j = 1; j < col; j++){
if (matrix[i][j] == '1')
dp[i][j] = dp[i][j-1] + 1;
}
}

for (int j = 0; j < col; j++){
for (int i = 0; i < row; i++){
if (matrix[i][j] == '0'){//think matrix[i][j] is the bottom right point of the rectangle, so if it is 0, then the area of
continue;            //rectangle is 0,
}

int min = dp[i][j]; // dp[i][j] means the bottom edge of the rectangle
for (int k = i; k >= 0 && matrix[i][j] == '1'; k--){//from bottom to top
if (min > dp[k][j]) // get the min edge from row k to i, which will consist the rectangle
min = dp[k][j];

if (min * (i-k+1) > max) // calculate the area of rectangle
max = min * (i-k+1);
}

}
}

return max;
}
``````

}

• "Timeout" means there is something wrong with the server.

Relax, try again later.

Happy Coding~

• Thanks:-). Change the subject.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.