Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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));
- }
- }
Add Comment
Please, Sign In to add comment