n участков, на каждом нужно построить по зданию. Для участка i задан предел высоты limits[i]: здание там должно иметь высоту от 1 до limits[i] включительно.
Силуэт улицы должен быть горкой: высоты не убывают до некоторого участка-вершины, а после него не возрастают. Вершина может быть у края улицы.
Верните наибольшую возможную сумму высот всех зданий.
Участков может быть до 10⁵, так что перебор вершины с проходом по всей улице для каждой не уложится по времени.limits=[2, 7, 3, 9, 1] → 18
Вершина на участке 3 (высота 9): слева высоты [2, 3, 3], справа 1. Ряд [2, 3, 3, 9, 1], сумма 18. Вершина на участке 1 дала бы [2, 7, 3, 3, 1] — 16.
limits=[5, 4, 4, 1] → 14
Ряд уже не возрастает, можно строить по пределам: 5 + 4 + 4 + 1 = 14.
limits=[6] → 6
limits[i] ≤ 10⁹limits=[2, 7, 3, 9, 1]
18
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 113 тестов на сервере, включая скрытые.