SHARE
TWEET

Untitled

a guest Jan 20th, 2019 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package ru.drone.ya;
  2.  
  3. public class MaxRectangleN3 {
  4.     /**
  5.      * Максимальная площадь прямоугольника в квадратной матрице
  6.      */
  7.     public long getMaxRectangleSquare(int[][] m) {
  8.         int[] cursor = new int[m.length];
  9.         long max = 0;
  10.         for (int row = 0; row < m.length; row++) {
  11.             for (int i = 0; i < cursor.length; i++)
  12.                 cursor[i] = m[row][i] == 0 ? 0 : cursor[i] + 1;
  13.             max = Long.max(max, getMaxRectangleSquare(cursor));
  14.         }
  15.         return max;
  16.     }
  17.  
  18.     /** a - строка с высотами*/
  19.     private long getMaxRectangleSquare(int[] a) {
  20.         long maxSq = a[0];
  21.         for (int left = 0; left < a.length; left++) {
  22.             long minH = a[left];//минимальная высота на отрезке от left до right
  23.             for (int right = left; right < a.length; right++) {
  24.                 minH = Long.min(minH, a[right]);
  25.                 maxSq = Long.max(maxSq, minH * (1 + right - left));
  26.             }
  27.         }
  28.         return maxSq;
  29.     }
  30.  
  31.     public static void main(String[] args) {
  32.         int[][] m = new int[][]{
  33.                 {1, 1, 1, 1, 1},
  34.                 {1, 1, 1, 1, 1},
  35.                 {1, 1, 1, 1, 1},
  36.                 {1, 1, 1, 1, 1},
  37.                 {1, 1, 1, 1, 1}
  38.         };
  39.         System.out.println("TEST 1 expected: 25, actual: " + new MaxRectangleN3().getMaxRectangleSquare(m));
  40.  
  41.         m = new int[][]{
  42.                 {0, 0, 1, 1, 1},
  43.                 {0, 0, 1, 0, 1},
  44.                 {1, 1, 1, 1, 0},
  45.                 {1, 0, 1, 1, 1},
  46.                 {1, 1, 1, 1, 0}
  47.         };
  48.         System.out.println("TEST 2 expected: 6, actual: " + new MaxRectangleN3().getMaxRectangleSquare(m));
  49.  
  50.         m = new int[][]{
  51.                 {0, 1, 1, 1, 1},
  52.                 {1, 1, 1, 1, 1},
  53.                 {1, 1, 1, 1, 1},
  54.                 {1, 1, 1, 1, 1},
  55.                 {1, 1, 1, 0, 1}
  56.         };
  57.         System.out.println("TEST 3 expected: 16, actual: " + new MaxRectangleN3().getMaxRectangleSquare(m));
  58.  
  59.     }
  60. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top