1. Maximum square submatrix. Given an n-by-n matrix of 0s and 1s, find a contiguous square submatrix of maximum size that contains only 1s. To do so, organize your program according to the following public API:

   public class MaximumSquareSubmatrix { // Returns the size of the largest contiguous square submatrix // of a[][] containing only 1s. public static int size(int[][] a) // 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) } 

   Here is some more information about the required behavior:

   • Size. The size of a square submatrix is its number of rows (or columns). You may assume that argument to the size() method is a square matrix containing only 0s and 1s.

   • Contiguous. The square submatrix must be contiguousthe row indicies must be consecutive and the column indices must be consecutive.

   • Performance. The size() method should take time proportional to n2n2 in the worst case. Significant partial credit for solutions that take time proportional to n3n3 or n4n4.

   • Input format. Standard input will contain a positive integer n, followed by n lines, with each line containing n 0s and 1s, separated by whitespace.

   Here are a few sample executions:

   ~/Desktop/performance> cat square6.txt 6 0 1 1 0 1 1 1 1 0 1 0 1 0 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 1 ~/Desktop/performance> java-introcs MaximumSquareSubmatrix  3 ~/Desktop/performance> cat square7.txt 7 0 1 1 0 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 0 1 1 ~/Desktop/performance> java-introcs MaximumSquareSubmatrix  4 

   The maximum square submatrix problem is related to problems that arise in databases, image processing, and maximum likelihood estimation. It is also a popular technical job interview question.

3. Maximum square submatrix. Given an nbyn matrix of 0s and 1s, find a contiguous square submatrix of maximum size that contains only 1s. To do so, organize your program according to the following public API: Here is some more information about the required behavior: - Size. The size of a square submatrix is its number of rows (or columns). You may assume that argument to the size() method is a square matrix containing only 0s and 1s. - Contiguous. The square submatrix must be contiguous - the row indicies must be consecutive and the column indices must be consecutive. Performance. The size () method should take time proportional to n2 in the worst case. Significant partial credit for solutions that take time proportional to n3 or n4. - Input format. Standard input will contain a positive integer n, followed by n lines, with each line containing n0 s and Is, separated by whitespace. Here are a few sample executions: The maximum square submatrix problem is related to problems that arise in databases, image processing and maximan likelihood estimation. It is also a popular technical job intenviev