Максимальная площадь прямоугольника в квадратной матрице за O(N^2)

MaxRectangleN2.java

package ru.drone.ya;

public class MaxRectangleN2 {
    /**
     * Максимальная площадь прямоугольника в квадратной матрице
     */
    public long getMaxRectangleSquare(int[][] m) {
        int n = m.length;
        if (n == 0) return 0;
        int[] cursor = new int[n];//высота. Как много можно подняться вверх чтобы получилась линия
        int[] leftLineShift = new int[n];//сколько идти влево чтобы была непрерывная линия
        int[] leftRectangle = new int[n];//накопительный итог по предыдущим рядам сколько можно идти влево чтобы построить прямоугольник высоты  cursor[i]
        int[] rightLineShift = new int[n];
        int[] rightRectangle = new int[n];

        long max = 0;
        for (int row = 0; row < n; row++) {
            for (int i = 0; i < n; i++) cursor[i] = m[row][i] == 0 ? 0 : cursor[i] + 1;

            leftLineShift[0] = m[row][0] == 0 ? 0 : 1;
            for (int i = 1; i < n; i++) leftLineShift[i] = m[row][i] == 0 ? 0 : leftLineShift[i - 1] + 1;
            for (int i = 0; i < n; i++)
                if (m[row][i] == 0) leftRectangle[i] = 0;//если в матрице сейчас 0, то пишем 0
                // если предыдущая 0, то высоту начали снова с 1. Пишем из тещущей строки.
                // если продолжаем серию, то минимум
                else leftRectangle[i] = leftRectangle[i] == 0? leftLineShift[i] : Integer.min(leftRectangle[i], leftLineShift[i]);

            rightLineShift[n-1] = m[row][n-1] == 0 ? 0 : 1;
            for (int i = n - 2; i >= 0; i--) rightLineShift[i] = m[row][i] == 0 ? 0 : rightLineShift[i + 1] + 1;
            for (int i = n - 1; i >= 0; i--)
                if (m[row][i] == 0) rightRectangle[i] = 0;
                else rightRectangle[i] = rightRectangle[i] == 0 ? rightLineShift[i] : Integer.min(rightRectangle[i], rightLineShift[i]);

            for (int i = 0; i < n; i++) max = Long.max(max, cursor[i] * (rightRectangle[i] + leftRectangle[i] -1));
        }
        return max;
    }

    public static void main(String[] args) {
        int[][] m = new int[][]{
                {1, 1, 1, 1, 1},
                {1, 1, 1, 1, 1},
                {1, 1, 1, 1, 1},
                {1, 1, 1, 1, 1},
                {1, 1, 1, 1, 1}
        };
        System.out.println("TEST 1 expected: 25, actual: " + new MaxRectangleN2().getMaxRectangleSquare(m));

        m = new int[][]{
                {0, 0, 1, 1, 1},
                {0, 0, 1, 0, 1},
                {1, 1, 1, 1, 0},
                {1, 0, 1, 1, 1},
                {1, 1, 1, 1, 0}
        };
        System.out.println("TEST 2 expected: 6, actual: " + new MaxRectangleN2().getMaxRectangleSquare(m));

        m = new int[][]{
                {0, 1, 1, 1, 1},
                {1, 1, 1, 1, 1},
                {1, 1, 1, 1, 1},
                {1, 1, 1, 1, 1},
                {1, 1, 1, 0, 1}
        };
        System.out.println("TEST 3 expected: 16, actual: " + new MaxRectangleN2().getMaxRectangleSquare(m));
    }
}