Rectángulo más Largo
El ogro Ork está planeando demoler un número de viejos edificios desocupados y construir un centro comercial en su lugar. Para ello necesita que Usted encuentre la mayor área sólida en la que se pueda construir el centro comercial. Los edificios que se elijan para construir el centro comercial tienen que ser consecutivos.
Se tienen edificios, cada uno de ellos tiene una altura . Si se unen edificios adyacentes partiendo del edificio se forma un rectángulo sólido de área .
Por ejemplo si se eligen tres edificios consecutivos con altura se crea un área sólida con altura y longitud , el valor del área es .
Entrada
La primera línea contiene un número entero , la cantidad de edificios.
La segunda línea contiene enteros separados por espacios en blanco, cada uno representa la altura de un edificio.
Salida
La primera y única línea de salida contiene un número entero, el área del mayor rectángulo formado.
Ejemplo de Entrada
5
1 2 3 4 5
Ejemplo de Salida
9
Explicación del Ejemplo
Se eligen tres edificios a partir del tercero , la longitud es , luego el área es .
Comments
Necesito ayuda en el problema de multiplicación en rango, q alguien me ayude
hacer dos bucles da AC porque los casos de prueba estan flojos.Esa solución es O(n^2).si pruebas un caso con los números desde 1 hasta 10^5 en orden,tardarias aproximadamente 100 segundos.
Una solucion bastante óptima es simplemente buscar para cada posición 'i' hasta q posición 'r' (r>i) se extiende el área y luego para 'l' (l<i). D esa forma con q aumentes un contador en 1 mientras buscas esos límites mediante 2 bucles o una Búsqueda Binaria, al final dices: sol = max(sol, cont*arr[i])
una cosa es óptima o no lo es, no puede ser bastante óptima, decir eso es lo mismo que decir más mejor.
yo aquí hablando de O(n) y la sengunda solucion mas rapida es O(n^2) tremendos casos de prueba
hay una solución en O(n).en vez de computar los extremos de los rangos con sparse table o segment tres lo haces con una pila
Cierto
alguien me puede ayudar con este trouble?
Solución en : para cada posición vamos a computar el rectángulo de máxima área cuya altura sea igual a la altura de esa posición. Para hacer eso, basta con buscar para la posición la menor posición y la mayor posición , entonces el mayor rectángulo de altura que contiene a tiene área , para computar y podemos hacer búsqueda binaria con alguna estructura de datos que compute mínimo en rangos como Sparse Table. La solución sería el .