Maximum size square sub-matrix with all 1s

Given a binary matrix, find out the maximum size square sub-matrix with all 1s.
Algorithm:
Let the given binary matrix be M[R][C].
The idea of the algorithm is to construct an auxiliary size matrix S[][] in which each entry S[i][j] represents size of the square sub-matrix with all 1s including M[i][j] and M[i][j] is the rightmost and bottommost entry in sub-matrix.
1) Construct a sum matrix S[R][C] for the given M[R][C].
     a) Copy first row and first columns as it is from M[][] to S[][]
     b) For other entries, use following expressions to construct S[][]
         If M[i][j] is 1 then
            S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
         Else /*If M[i][j] is 0*/
            S[i][j] = 0
2) Find the maximum entry in S[R][C]
3) Using the value and coordinates of maximum entry in S[i], print
   sub-matrix of M[][]
Java Code : 

public class MaxSubMatrix {
 public static void main(String[] args) {
  int[][] a = { 
                 { 0, 1, 1, 0, 1 }, 
                 { 1, 1, 0, 1, 0 }, 
                 { 0, 1, 1, 1, 0 },
                 { 1, 1, 1, 1, 0 }, 
                 { 1, 1, 1, 1, 1 }, 
                 { 0, 0, 0, 0, 0 } 
           };

  int rows = a.length;
  int columns = a[0].length;

  int[][] S = new int[rows][columns];

  // fill first row elements from a as it is
  for (int i = 0; i < columns; i++) {
   S[0][i] = a[0][i];
  }

  // similarly fill all elements in first column
  for (int i = 0; i < rows; i++) {
   S[i][0] = a[i][0];
  }

  // now calculate for other elements
  for (int i = 1; i < rows; i++) {
   for (int j = 1; j < columns; j++) {
    if (a[i][j] == 1)
     S[i][j] = getMinimum(S[i - 1][j], S[i][j - 1],
       S[i - 1][j - 1]) + 1;
   }
  }

  // Traverse the array and find the maximum value in array
  int maxSubMatrixSize = 0;
  int maxRowIndex = 0;
  int maxColumnIndex =0;
  for (int i = 0; i < rows; i++) {
   for (int j = 0; j < columns; j++) {
    if (S[i][j] > maxSubMatrixSize)
        maxSubMatrixSize = S[i][j];
        maxRowIndex= i;
        maxColumnIndex = j;
   }
  }
  System.out.println("Maximum size of submatrix with all ones : "
    + maxSubMatrixSize);
  System.out.println("Sub matrix starts from "+ (maxSubMatrixSize-1) + " positions above diagonally from position a["+maxRowIndex+"]["+maxColumnIndex+"]");   
 }

 private static int getMinimum(int a, int b, int c) {
  int min = a;
  if (a <= b && a <= c)
   min = a;
  else
   min = (b <= a && b <= c) ? b : c;
  return min;
 }

}

Time Complexity: O(m*n) where m is number of rows and n is number of columns in the given matrix.
Auxiliary Space: O(m*n) where m is number of rows and n is number of columns in the given matrix.

Refer : http://www.geeksforgeeks.org/archives/6257