Zone rectangulaire maximale dans un histogramme
Étant donné
n nombres représentant les hauteurs des barres d’un histogramme, il est demandé de calculer la plus grande surface possible sans dépasser les limites des barres.Toutes les barres de l’histogramme ont une largeur de 1, et leurs hauteurs sont des entiers non négatifs arbitraires.
Entrée
La première ligne de l’entrée contient un unique entier
n (1 ≤ n ≤ ).La ligne suivante contient
n entiers séparés par des espaces (0 ≤ ≤ ).Sortie
Le programme doit afficher la plus grande surface pouvant être obtenue à partir des barres de l’histogramme.
Exemples
Entrée | Sortie |
8
6 2 5 4 5 1 6 1 | 12 |
Indice
Pour chaque élément de l’histogramme, vous pouvez déterminer deux positions : l’élément le plus proche, à gauche, qui est plus petit que l’élément actuel, ainsi que celui à droite. Ces deux informations suffisent pour calculer la surface du rectangle ayant la hauteur de la barre courante.
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB