Guest User

Untitled

a guest
Jan 20th, 2019
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.22 KB | None | 0 0
  1. package ru.drone.ya;
  2.  
  3. public class MaxRectangleN2 {
  4. /**
  5. * Максимальная площадь прямоугольника в квадратной матрице
  6. */
  7. public long getMaxRectangleSquare(int[][] m) {
  8. int n = m.length;
  9. if (n == 0) return 0;
  10. int[] cursor = new int[n];//высота. Как много можно подняться вверх чтобы получилась линия
  11. int[] leftLineShift = new int[n];//сколько идти влево чтобы была непрерывная линия
  12. int[] leftRectangle = new int[n];//накопительный итог по предыдущим рядам сколько можно идти влево чтобы построить прямоугольник высоты cursor[i]
  13. int[] rightLineShift = new int[n];
  14. int[] rightRectangle = new int[n];
  15.  
  16. long max = 0;
  17. for (int row = 0; row < n; row++) {
  18. for (int i = 0; i < n; i++) cursor[i] = m[row][i] == 0 ? 0 : cursor[i] + 1;
  19.  
  20. leftLineShift[0] = m[row][0] == 0 ? 0 : 1;
  21. for (int i = 1; i < n; i++) leftLineShift[i] = m[row][i] == 0 ? 0 : leftLineShift[i - 1] + 1;
  22. for (int i = 0; i < n; i++)
  23. if (m[row][i] == 0) leftRectangle[i] = 0;//если в матрице сейчас 0, то пишем 0
  24. // если предыдущая 0, то высоту начали снова с 1. Пишем из тещущей строки.
  25. // если продолжаем серию, то минимум
  26. else leftRectangle[i] = leftRectangle[i] == 0? leftLineShift[i] : Integer.min(leftRectangle[i], leftLineShift[i]);
  27.  
  28. rightLineShift[n-1] = m[row][n-1] == 0 ? 0 : 1;
  29. for (int i = n - 2; i >= 0; i--) rightLineShift[i] = m[row][i] == 0 ? 0 : rightLineShift[i + 1] + 1;
  30. for (int i = n - 1; i >= 0; i--)
  31. if (m[row][i] == 0) rightRectangle[i] = 0;
  32. else rightRectangle[i] = rightRectangle[i] == 0 ? rightLineShift[i] : Integer.min(rightRectangle[i], rightLineShift[i]);
  33.  
  34. for (int i = 0; i < n; i++) max = Long.max(max, cursor[i] * (rightRectangle[i] + leftRectangle[i] -1));
  35. }
  36. return max;
  37. }
  38.  
  39. public static void main(String[] args) {
  40. int[][] m = new int[][]{
  41. {1, 1, 1, 1, 1},
  42. {1, 1, 1, 1, 1},
  43. {1, 1, 1, 1, 1},
  44. {1, 1, 1, 1, 1},
  45. {1, 1, 1, 1, 1}
  46. };
  47. System.out.println("TEST 1 expected: 25, actual: " + new MaxRectangleN2().getMaxRectangleSquare(m));
  48.  
  49. m = new int[][]{
  50. {0, 0, 1, 1, 1},
  51. {0, 0, 1, 0, 1},
  52. {1, 1, 1, 1, 0},
  53. {1, 0, 1, 1, 1},
  54. {1, 1, 1, 1, 0}
  55. };
  56. System.out.println("TEST 2 expected: 6, actual: " + new MaxRectangleN2().getMaxRectangleSquare(m));
  57.  
  58. m = new int[][]{
  59. {0, 1, 1, 1, 1},
  60. {1, 1, 1, 1, 1},
  61. {1, 1, 1, 1, 1},
  62. {1, 1, 1, 1, 1},
  63. {1, 1, 1, 0, 1}
  64. };
  65. System.out.println("TEST 3 expected: 16, actual: " + new MaxRectangleN2().getMaxRectangleSquare(m));
  66. }
  67. }
Add Comment
Please, Sign In to add comment