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