Maior Área Retangular num Histograma
Dado
n números que representam as alturas de barras num histograma, é solicitado que se calcule a maior área que pode ser obtida no histograma sem ultrapassar as barras.Todas as barras do histograma têm uma largura de 1, enquanto as alturas são inteiros não negativos arbitrários.
Entrada
A primeira linha da entrada contém um único inteiro
n (1 ≤ n ≤ ).A linha seguinte contém
n inteiros separados por espaços (0 ≤ ≤ ).Saída
O programa deve imprimir a maior área possível de obter a partir das barras do histograma.
Exemplos
Entrada | Saída |
8
6 2 5 4 5 1 6 1 | 12 |
Dica
Para cada elemento do histograma, é possível calcular dois valores: o elemento mais próximo à esquerda e o mais próximo à direita que sejam menores que o elemento atual. Isso é suficiente para determinar a área do retângulo com a altura da barra em questão.
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB