# Java short dp solution, beats 75%. 2 lines commented code matters the run time!

• ``````public int maximalRectangle(char[][] matrix) {
if(matrix.length==0||matrix[0].length==0) return 0;
int m = matrix.length;
int n = matrix[0].length;
int maxres = 0;
int[][] mostleft = new int[m][n];
int[][] mosttop = new int[m][n];
for(int i = 0;i<m;i++){
for(int j = 0;j<n;j++){
if(matrix[i][j]=='1'){
if(i>0) mosttop[i][j] = mosttop[i-1][j]+1;
else mosttop[i][j] = 1;
if(j>0) mostleft[i][j] = mostleft[i][j-1]+1;
else mostleft[i][j] = 1;
}
}
}
for(int i = m-1;i>=0;i--){
for(int j = n-1;j>=0;j--){
if((i+1)*(j+1)<=maxres) break;//cannot find a bigger rectangle.
if(matrix[i][j]=='1'){
int leftlen = mostleft[i][j];
int currmax = 0;
int minheight = m;
for(int wid = 0;wid<leftlen;wid++){
int currheight = mosttop[i][j-wid];
minheight = minheight>currheight?currheight:minheight;
if(minheight*leftlen<maxres) break;//Another line to make the loop end faster.
int currsize = minheight*(wid+1);
currmax = currmax>currsize?currmax:currsize;
}
if(currmax>maxres) maxres = currmax;
}
}
}
return maxres;
}``````

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