Наибольшая площадь прямоугольника в гистограмме
Дано n чисел, задающих высоты столбцов в гистограмме. Нужно вычислить максимальную площадь, которую можно получить внутри гистограммы, не выходя за границы столбцов.
Все столбцы в гистограмме имеют ширину 1, а их высоты задаются произвольными неотрицательными целыми числами.
Вход
Первая строка входных данных содержит одно целое число n (1 ≤ n ≤ ).
Во второй строке записаны n целых чисел через пробел: (0 ≤ ≤ ).
Вывод
Программа должна вывести максимальную площадь, которую можно получить из столбцов гистограммы.
Примеры
Ввод | Вывод |
|---|---|
8 | 12 |
Подсказка
Для каждого элемента гистограммы можно найти 2 индекса — ближайший меньший элемент слева и ближайший меньший элемент справа. Эти данные позволят вычислить площадь прямоугольника с высотой, равной высоте текущего столбца.
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB