Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- import java.lang.*;
- public class Main {
- public static void main(String[] args) {
- new Main().solve();
- }
- public void solve() {
- Scanner scanner = new Scanner(System.in);
- int n = scanner.nextInt();
- int[][] a = new int[n][n];
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < n; j++) {
- a[i][j] = scanner.nextInt();
- }
- }
- int answer = findMaxOnesSquare(a);
- System.out.printf("Max ones rectangle square is %d.\n", answer);
- }
- private int findMaxOnesSquare(int[][] a) {
- int n = a.length;
- int[] onesUp = new int[n];
- int answer = 0;
- for (int row = 0; row < n; row++) {
- Stack<Integer> prevColumns = new Stack<>();
- for (int column = 0; column < n; column++) {
- if (a[row][column] == 1) {
- onesUp[column]++;
- } else {
- onesUp[column] = 0;
- }
- int curHeight = onesUp[column];
- while (!prevColumns.isEmpty()) {
- int prevPos = prevColumns.peek();
- if (onesUp[prevPos] < curHeight) {
- break;
- } else {
- int curMax = curHeight * (column - prevPos + 1);
- answer = Math.max(answer, curMax);
- prevColumns.pop();
- }
- }
- prevColumns.push(column);
- }
- while (!prevColumns.isEmpty()) {
- int prevPos = prevColumns.pop();
- int curMax = onesUp[prevPos] * (n - prevPos);
- answer = Math.max(answer, curMax);
- }
- }
- return answer;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement