package ru.drone.ya;

public class MaxRectangleN3 {
    /**
     * Максимальная площадь прямоугольника в квадратной матрице
     */
    public long getMaxRectangleSquare(int[][] m) {
        int[] cursor = new int[m.length];
        long max = 0;
        for (int row = 0; row < m.length; row++) {
            for (int i = 0; i < cursor.length; i++)
                cursor[i] = m[row][i] == 0 ? 0 : cursor[i] + 1;
            max = Long.max(max, getMaxRectangleSquare(cursor));
        }
        return max;
    }

    /** a - строка с высотами*/
    private long getMaxRectangleSquare(int[] a) {
        long maxSq = a[0];
        for (int left = 0; left < a.length; left++) {
            long minH = a[left];//минимальная высота на отрезке от left до right
            for (int right = left; right < a.length; right++) {
                minH = Long.min(minH, a[right]);
                maxSq = Long.max(maxSq, minH * (1 + right - left));
            }
        }
        return maxSq;
    }

    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 MaxRectangleN3().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 MaxRectangleN3().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 MaxRectangleN3().getMaxRectangleSquare(m));

    }
}