MaximumSquareSubmatrix.java

/* *****************************************************************************
 *  Name:              Ada Lovelace
 *  Coursera User ID:  123456
 *  Last modified:     October 16, 1842
 **************************************************************************** */

public class MaximumSquareSubmatrix {
    // Returns the size of the largest contiguous square submatrix
    // of a[][] containing only 1s.
    public static int size(int[][] a) {
        int length = a.length;
        int[][] dp = new int[length + 1][length + 1];
        int maxSize = 0;

        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = a[i][j];
                    if (a[i][j] > maxSize) maxSize = a[i][j];
                }
                else {
                    if (a[i][j] == 1) {
                        dp[i][j] = Minimum(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
                        if (dp[i][j] >= maxSize)
                            maxSize = dp[i][j];
                    }
                }
            }
        }
        return maxSize;
    }

    private static int Minimum(int a, int b, int c) {
        int min1 = Math.min(a, b);
        int min2 = Math.min(min1, c);
        return min2;
    }

    // Reads an n-by-n matrix of 0s and 1s from standard input
    // and prints the size of the largest contiguous square submatrix
    // containing only 1s.
    public static void main(String[] args) {
        int n = StdIn.readInt();
        int[][] a = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                a[i][j] = StdIn.readInt();
            }
        }
        StdOut.print(size(a));
    }
}