Größte rechteckige Fläche in einem Histogramm
Angenommen, wir haben
n Zahlen, die die Höhen der Balken in einem Histogramm repräsentieren. Unsere Aufgabe besteht darin, ohne über die Balken hinauszugehen, die maximal mögliche Fläche zu ermitteln, die in diesem Diagramm entsteht.Alle Balken in diesem Histogramm haben eine Breite von 1. Die Höhen sind nichtnegative ganzzahlige Werte (also beliebig groß, aber mindestens Null).
Eingabe
Die erste Zeile der Eingabe enthält eine einzelne ganze Zahl
n (1 ≤ n ≤ ).Die nächste Zeile enthält
n durch Leerzeichen getrennte ganze Zahlen (0 ≤ ≤ ).Ausgabe
Das Programm soll die größtmögliche Fläche ausgeben, die anhand der Balken des Histogramms gebildet werden kann.
Beispiele
Input | Output |
8
6 2 5 4 5 1 6 1 | 12 |
Hinweis
Für jedes Element im Histogramm lassen sich zwei Werte bestimmen – die Position des nächstgelegenen kleineren Elements links und rechts. Diese Informationen reichen aus, um die Fläche eines Rechtecks zu berechnen, das die Höhe des aktuellen Balkens besitzt.
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB