Advertisement
Guest User

Untitled

a guest
Apr 24th, 2019
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.84 KB | None | 0 0
  1. import java.util.*;
  2. import java.lang.*;
  3.  
  4. public class Main {
  5.     public static void main(String[] args) {
  6.         new Main().solve();
  7.     }
  8.  
  9.     public void solve() {
  10.         Scanner scanner = new Scanner(System.in);
  11.         int n = scanner.nextInt();
  12.         int[][] a = new int[n][n];
  13.         for (int i = 0; i < n; i++) {
  14.             for (int j = 0; j < n; j++) {
  15.                 a[i][j] = scanner.nextInt();
  16.             }
  17.         }
  18.  
  19.         int answer = findMaxOnesSquare(a);
  20.         System.out.printf("Max ones rectangle square is %d.\n", answer);
  21.     }
  22.  
  23.     private int findMaxOnesSquare(int[][] a) {
  24.         int n = a.length;
  25.         int[] onesUp = new int[n];
  26.         int answer = 0;
  27.  
  28.         for (int row = 0; row < n; row++) {
  29.             Stack<Integer> prevColumns = new Stack<>();
  30.  
  31.             for (int column = 0; column < n; column++) {
  32.                 if (a[row][column] == 1) {
  33.                     onesUp[column]++;
  34.                 } else {
  35.                     onesUp[column] = 0;
  36.                 }
  37.  
  38.                 int curHeight = onesUp[column];
  39.                 while (!prevColumns.isEmpty()) {
  40.                     int prevPos = prevColumns.peek();
  41.                     if (onesUp[prevPos] < curHeight) {
  42.                         break;
  43.                     } else {
  44.                         int curMax = curHeight * (column - prevPos + 1);
  45.                         answer = Math.max(answer, curMax);
  46.  
  47.                         prevColumns.pop();
  48.                     }
  49.                 }
  50.  
  51.                 prevColumns.push(column);
  52.             }
  53.  
  54.             while (!prevColumns.isEmpty()) {
  55.                 int prevPos = prevColumns.pop();
  56.                 int curMax = onesUp[prevPos] * (n - prevPos);
  57.                 answer = Math.max(answer, curMax);
  58.             }
  59.         }
  60.  
  61.         return answer;
  62.     }
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement