Java DP solution


  • 0
    Z

    '''
    class Solution {
    public int maximalRectangle(char[][] matrix) {

        int rows = matrix.length;
        if(rows ==0 ) return 0;
        int cols = matrix[0].length;
        
        int[][] weight = new int[rows][cols];
        if(matrix[0][0] =='0') weight[0][0] = 0; 
        else weight[0][0]=1; 
    
        for (int i=0 ; i < rows; i++){
            for (int j =0 ; j < cols; j++){
                if(i ==0 && j==0 ) continue;
                else if (i==0) weight[i][j] = Math.max(weight[i][j-1],P(matrix ,i,j));
                else if(j==0) weight[i][j] = Math.max(weight[i-1][j],P(matrix ,i,j));
                else {
                    weight[i][j] = Math.max( weight[i-1][j], weight[i][j-1]);
                    weight[i][j] = Math.max(weight[i][j], P(matrix ,i,j));
                }
            }
        }
    
        return weight[rows-1][cols-1];
    }
    
    
    public int P (char[][] matrix , int i , int j){
        if(matrix[i][j]==0) return 0;
        
        // horizon
        int h = i, v =j;
        
        while(h >=0){
            if (matrix[h][j] =='0') break;
            h--;continue ;
        }
        while(v >=0){
            if (matrix[i][v] =='0') break;
            v--;continue ;
        }
        
        int ind =h;
        int val = Math.max (i-h,j-v);
        for (int m = j-1; m >v ; m-- ){
            for (int n = i; n >ind; n--){
                if(matrix[n][m] =='1') continue ;
                ind = n; break;
            }
            val = Math.max(val, (i-ind)*(j-m+1));
        }
        return val;
    }
    

    }
    '''


Log in to reply
 

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