SHARE
TWEET

Untitled

a guest Jun 19th, 2017 47 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public class MaximalSquare {
  2.     static int min(int a, int b, int c) {
  3.         return Math.min(a, Math.min(b, c));
  4.     }
  5.  
  6.     static int findMaxSquare(int[][] matrix) {
  7.         int n = matrix.length;
  8.         int m = matrix[0].length;
  9.         int[][] memo = new int[n][m];
  10.         int max = 0;
  11.         // initialize
  12.         // copy first column
  13.         for (int i = 0; i < n; i++) {
  14.             memo[i][0] = matrix[i][0];
  15.             max = Math.max(max, memo[i][0]);
  16.         }
  17.         // copy first row
  18.         for (int i = 1; i < m; i++) {
  19.             memo[0][i] = matrix[0][i];
  20.             max = Math.max(max, memo[0][i]);
  21.         }
  22.         // fill the rest
  23.         for (int i = 1; i < n; i++) {
  24.             for (int j = 1; j < m; j++) {
  25.                 if (matrix[i][j] == 1) {
  26.                     memo[i][j] = min(memo[i - 1][j], memo[i - 1][j - 1], memo[i][j - 1]) + 1;
  27.                 } else {
  28.                     memo[i][j] = 0;
  29.                 }
  30.                 max = Math.max(max, memo[i][j]);
  31.             }
  32.         }
  33.         return max * max;
  34.     }
  35.  
  36.     public static void main(String[] args) {
  37.         int[][] matrix = {
  38.                 {1, 0, 1, 0, 0},
  39.                 {1, 0, 1, 1, 1},
  40.                 {1, 1, 1, 1, 1},
  41.                 {1, 0, 0, 1, 0}
  42.         };
  43.         System.out.println(findMaxSquare(matrix));
  44.     }
  45. }
RAW Paste Data
Top