Ctrl K

Самый большой прямоугольник под силуэтом

Сложная
Город на картинке — ряд башен шириной 1, стоящих вплотную друг к другу. Высоты башен слева направо даны в массиве towers. Впишите в силуэт города прямоугольник со сторонами, параллельными осям, который опирается на землю и целиком лежит внутри башен. Верните наибольшую возможную площадь такого прямоугольника.
Пример 1
towers=[3, 1, 4, 4, 2, 5] → 8

Две башни высотой 4 стоят рядом: прямоугольник 4 × 2 = 8. Прямоугольник высотой 2 на башнях с индексами 2–5 даёт тоже 8, а больше не получится.

Пример 2
towers=[2, 2, 2, 2] → 8

Весь ряд одной высоты: 2 × 4 = 8.

Пример 3
towers=[0, 6, 0] → 6

Ширина ограничена нулями по краям: 6 × 1 = 6.

Ограничения
  • 1 ≤ len(towers) ≤ 10⁵
  • 0 ≤ towers[i] ≤ 10⁴
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиВода между стенами СложнаяСамый большой горящий блок СложнаяНаибольшее число из двух рядов СложнаяПартии для сортировки с повторами СложнаяЛягушка на столбиках Сложная
загружаем Python…
Вход
towers=[3, 1, 4, 4, 2, 5]
Ожидается
8

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