题解 | #最大子方阵#

import java.util.*;

public class SubMatrix {
public int maxSubMatrix(int[][] mat, int n) {
// write code here
int[][] hang = new int[n][n];
int[][] lie = new int[n][n];
initial(n, hang, lie, mat);
int max = 1;
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
if (mat[i-1][j] == mat[i][j] && mat[i][j] == mat[i][j-1]) {
hang[i][j] = hang[i][j - 1] + 1;
lie[i][j] = lie[i - 1][j] + 1;
int len = Math.min(hang[i][j], lie[i][j]);
for (int k = 0;k < len; k++) {
if (k+1 > max && hang[i-k][j] > k && lie[i][j-k] > k) {
max = k+1;
break;
}
}
} else if (mat[i-1][j] == mat[i][j]) {
lie[i][j] = lie[i-1][j] + 1;
hang[i][j] = 1;
} else if (mat[i][j-1] == mat[i][j]) {
hang[i][j] = hang[i][j-1] + 1;
lie[i][j] = 1;
} else {
hang[i][j] = 1;
lie[i][j] = 1;
}
}
}
return max;
}

public void initial(int n, int[][] hang, int[][] lie, int[][] mat) {
    for (int i = 0; i < n; i++) {
        hang[i][0] = 1;
        lie[0][i] = 1;
    }
    for (int i = 1; i < n; i++) {
        if (mat[0][i] == mat[0][i - 1]) {
            hang[0][i] = hang[0][i - 1] + 1;
        } else {
            hang[0][i] = 1;
        }
    }
    for (int i = 1; i < n; i++) {
        if (mat[i][0] == mat[i - 1][0]) {
            lie[i][0] = lie[i - 1][0] + 1;
        } else {
            lie[i][0] = 1;
        }
    }
}

}