Ctrl K

Блок единиц после перестановки столбцов

Средняя
Дана таблица board из нулей и единиц. Её столбцы разрешено переставить в любом порядке (столбец переезжает целиком, строки остаются на своих местах). После перестановки найдите прямоугольный блок соседних клеток, целиком состоящий из единиц. Верните наибольшую площадь такого блока при лучшей перестановке столбцов. Если единиц нет, ответ 0.
Пример 1
board=[[1, 0, 1, 1], [1, 1, 0, 1], [1, 1, 1, 1]] → 6

Столбцы 0 и 3 целиком из единиц. Поставим их рядом — получится блок 3×2 площадью 6.

Пример 2
board=[[0, 1, 0, 1, 1]] → 3

Три единицы можно собрать подряд: блок 1×3.

Пример 3
board=[[1, 0], [0, 1]] → 1

Как ни переставляй столбцы, единицы в разных строках, так что блок — одна клетка.

Ограничения
  • 1 ≤ число строк × число столбцов ≤ 10⁵
  • Все строки одной длины
  • board[i][j] — 0 или 1
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиЛучшие предметы с полок СредняяПотратить как можно больше СложнаяСамое большое число из кусков СредняяСтудии для записи СредняяНизко — высоко — низко Средняя
загружаем Python…
Вход
board=[[1, 0, 1, 1], [1, 1, 0, 1], [1, 1, 1, 1]]
Ожидается
6

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 86 тестов на сервере, включая скрытые.