*Java* Straightforward DP Solution


  • 0
    E
    public class Solution {
    
    public int maximalSquare(char[][] matrix) {
    	int m = matrix.length;
    	if(m<1) return 0;
    	int n = matrix[0].length;
    	int[][] res = new int[m][n];
    	int max = 0; // maximum area
    	for(int i=0; i<m; i++) { // initilize first column
    		res[i][0] = matrix[i][0] - '0';
    		max += res[i][0];
    	}
    	for(int j=1; j<n; j++) { // initilize first row
    		res[0][j] = matrix[0][j] - '0';
    		max += res[0][j];
    	}
    	max = max > 0 ? 1 : 0; // correct max value
    	for(int i=1; i<m; i++) {
    		for(int j=1; j<n; j++) {
    			res[i][j] = (matrix[i][j]=='0') ? 0 : min3(res[i-1][j-1], res[i][j-1], res[i-1][j])+1;
    			int temp = res[i][j] * res[i][j];
    			max = temp > max ? temp : max; // update max
    		}
    	}
    	return max;
    }
    // min of three ints:
    private int min3(int a, int b, int c) {
    	int minab = a < b ? a : b;
    	return c < minab ? c : minab; 
    }
    }

Log in to reply
 

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