Área Máxima de un Rectángulo en un Histograma
Dado
n números que representan las alturas de las barras en un histograma, se te pide calcular el área más grande que se pueda obtener dentro de las barras.Todas las barras del histograma tienen un ancho de 1, mientras que sus alturas son números enteros no negativos de cualquier tamaño.
Entrada
La primera línea de la entrada contiene un único número entero
n (1 ≤ n ≤ ).La siguiente línea contiene
n números enteros separados por espacio (0 ≤ ≤ ).Salida
El programa debe imprimir el área más grande posible que se pueda formar con las barras del histograma.
Ejemplos
Entrada | Salida |
8
6 2 5 4 5 1 6 1 | 12 |
Pista
Para cada elemento del histograma, puedes calcular dos valores: el elemento más cercano a la izquierda que sea menor que el actual y el más cercano a la derecha que sea menor que el actual. Con ello resulta suficiente para determinar el área del rectángulo que tenga como altura la barra actual.
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB