Today we continue discussing the problem of finding largest sub matrix of 1 in a boolean matrix using graph based method. we were saying that the depth first search  allows us to explore islands of ones one after the other. This way we could count the number of islands. Furthermore we could find the size of each island. we could now tell the largest island. It was however not clear how to find the submatrix contained within an island given that the island could be of irregular shape. In order to find the contained matrix, we merely have to find the corners. we know when we enter an island so we can initialize the minimum and maximum row and columns encountered. Candidates for corners are initialized by the min and max of row,column encountered in that island as the case maybe for that direction. for example, top left will require both row and column value to be minimum. Then the coordinates at these boundary values or adjacent to it such that the area of the sub matrix contained is maximized are used as corners. Therefore we pick the common values for coordinates as close to the corners as possible. for example the sub matrix will have a top row as the higher row value of top left and top right corners. this gives us the submatrix for each island. This method is equally applicable to the largest island as it is applicable to other islands.
#untested but just for explanation.
Tuple<int, int> GetTopLeft(int[,] A, int ROW  int COL, int sr, int sc)
{
assert(A[sr,  sc] == 1); // arbitrary starting point an island
int minr = sr;
int minc = sc;
int maxr = sr:
int maxc = sc;
bool change = True;
while(change)
{
change = False;
for(int k = minr-1; k >= 0 && A[k, minc] && A[k, maxc] ; k--) {minr--; change = True;}
for(int k = maxr+1; k  < ROW  && A[k, minc] && A[k, maxc] ; k++) {maxr++;change = True;}
for(int k = minc-1; k >= 0 && A[minr, k] && A[maxr,k] ; k--) {minc--;change = True;}
for(int k = maxc+1; k < COL  && A[minr, k]  && A[maxr,k]; k++) {maxc++;change = True;}
}
return new Tuple<int, int> (minr, minc);
}