#leetcode #medium #google #directi 1727. Largest Submatrix With Rearrangements Дейлик литкода 17.03.2026 You are given a binary matrix matrix of size m x n, and you are allowed to rearrange the columns of the matrix in any order. Return the area of the largest submatrix within matrix where every element of the submatrix is 1 after reordering the columns optimally. Идея: Максимальная площадь прямоугольника из единиц = ширина × высота. Строки переставлять нельзя → высота фиксирована. Столбцы переставлять можно → ширину можно максимизировать. Основной приём: Для каждой строки считаем, сколько непрерывных единиц идёт вверх от текущей клетки в каждом столбце (высота гистограммы). Алгоритм кратко: Проходим по строкам сверху вниз. Для каждой строки: Обновляем высоты: если matrix[row][col] == 1 → height[col] = height[col] + 1 иначе height[col] = 0 Делаем копию массива высот → сортируем по убыванию Проходим по отсортированному массиву: Для каждого i: площадь = sorted[i] × (i + 1) Обновляем максимум class Solution { public int largestSubmatrix(int[][] matrix) { int n = matrix.length, m = matrix[0].length; int[] currRow = new int[m]; int[] tmpRow = new int[m]; int ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { currRow[j] = matrix[i][j] == 1 ? currRow[j] + 1 : 0; } tmpRow = Arrays.copyOf(currRow, m); Arrays.sort(tmpRow); ans = Math.max(ans, tmpRow[m - 1]); for (int j = m - 2; j >= 0; j--) { ans = Math.max(ans, (m - j) * tmpRow[j]); } } return ans; } }