Find largest block in matrix
There is a neat trick in many computer algorithms called memoization - the remembering of critical aspects of one computation, to reuse them in another. Memoization can help a lot in this problem. To explain this, consider the basic algorithm you have...


start at the top-left of the matrix
scan every position in the matrix
for each position, check whether it is the top-left of an increasing square of set values.
keep track of the maximum.


This process is effective, but not very efficient. What if I were to tell you there is a way to solve the problem without having to do step 3, just by remembering what you did in previous iterations of step 1 and 2?

The way we do things, is to remember the size of previously-computed squares of set positions. We remember the previous row, and the current row only. No need to remember more than that....

Looking at your example:

1 0 1 0 1 
1 1 1 0 1 
1 0 1 1 1 
1 0 1 1 1 
1 0 1 1 1


It is a matrix of size 5. We create two temporary arrays to record the previous and current memoization:

int[] previous = new int[5];
int[] current = new int[5];


Now, we compute the values for the current memoization - it works like this:


if the cell in the current column is not set, then the square at the current position is size 0.
if the cell is set, then it is 1 more than the smallest square above , above-left, or left of it. This needs a picture.....



As you can see, I have marked 3 squares - red, blue, and purple. Each of them is 2x2. The position at the bottom right, is the end of the 3x3 square. it is 1 + the minimum size of the blue, red, and purple squares.


So, it becomes relatively simple to identify squares, we only need to check three values for each cell.... the code is surprisingly simple, even if the concept is hard...

private static Square getLargestSquare(int[][] matrix) {
    if (matrix == null || matrix.length == 0) {
        return null;
    }

    final int height = matrix.length;
    final int width = matrix[0].length;

    Square max = null;

    // cheat, here, and use the first matrix row as 'current'
    // this will become 'previous' in the loop, and will not be changed.
    // note that the y-loop starts from 1, not 0.
    int[] previous = null;
    int[] current = matrix[0];

    for (int y = 1; y &lt; height; y++) {
        // prepare the memoization space.
        // Forget the previous, move current back, and make a new current
        previous = current;
        current = new int[width];
        for (int x = 0; x &lt; width; x++) {
            if (matrix[y][x] == 1) {
                int span = 1;
                if (x &gt; 0) {
                    // no need to check the left-most column, if set, it is always size 1.
                    span = 1 + Math.min(current[x - 1], Math.min(previous[x], previous[x - 1]));
                }
                if (max == null || span &gt; max.size) {
                    // because we find the max at x, and y, which are the bottom-right,
                    // we need to subtract the span to get to the top-left instead.
                    max = new Square(x - span + 1, y - span + 1, span);
                }
                current[x] = span;
            }
        }
    }

    return max;
}


Note that I have created a container-class Square to hold the result:

private static final class Square {
    private final int x, y, size;

    public Square(int x, int y, int size) {
        super();
        this.x = x;
        this.y = y;
        this.size = size;
    }

    @Override
    public String toString() {
        return String.format("Square at (%d,%d) is size %d", x, y, size);
    }

}


Additionally, the main method is now simple:

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

    Square sq = getLargestSquare(matrix);

    System.out.println("Largest square: " + sq);
}


You can see the whole thing on ideone: Largest Square