Teniendo un arreglo de números, queremos encontrar la suma máxima que podemos obtener utilizando únicamente casillas adyacentes. Podemos resolver este problema rápidamente utilizando un ciclo para indicar donde empieza el arreglo, otro para indicar donde termina y uno más para encontrar la suma, con lo que tendríamos un algoritmo O(n3). Sin embargo, aprovechando las ventajas de programación dinámica podemos obtener un algoritmo O(n).
Supongamos que ya tenemos la suma máxima que termina en i, para saber la suma máxima que termina en i+1 tenemos dos opciones: agregar la casilla i+1 a la suma que llega hasta i o empezar una nueva que sólo tenga la casilla i+1. Tomamos el mayor de estos números.
Problema ejemplo
Híper-brinco
Problema
Desarrollado a principios del siglo XXI, el híper-brinco sigue siendo el principal medio de transportación para distancias de hasta miles de parsecs. Pero recientemente los físicos han descubierto un fenómeno increíble. Creen que la duración de la fase alfa del híper-brinco puede ser controlada con facilidad. La fase alfa es el período en el cual la híper-nave acumula el potencial gravitacional. Entre más grande sea el potencial gravitacional acumulado, menos energía es requerida para realizar el híper-brinco. Tu trabajo es escribir un programa que ayude a los pilotos a decidir cuando entrar y salir de la fase de híper-brinco, de tal forma que la híper-nave acumule la mayor cantidad posible de potencial gravitacional.El modelo más básico del campo gravitatorio (el cual estarás usando) obtiene una serie de números enteros pi (1 ≤ i ≤ n), los cuales representan intensidades del campo a través de distintos momentos en el tiempo. De acuerdo a este modelo, si la fase alfa comienza en el instante i y termina en el instante j, entonces el valor del potencial gravitacional será igual a la suma de los elementos de la serie que se encuentran desde el i-ésimo hasta el j-ésimo de forma inclusiva.
Entrada
La primera línea de la entrada contiene solamente un entero n que es la cantidad de elementos en la serie (n < 60000). Las siguientes n líneas indican los elementos de la serie, cada línea conteniendo a un único entero pi (-30000 ≤ pi ≤ 30000). La primera de éstas n líneas contiene a p1, la segunda a p2, y así sucesivamente.Salida
Solo una línea aparece en la salida, la cual contiene el valor más grande posible del potencial gravitacional que puede ser acumulado por la híper-nave durante la fase alfa. Deberás asumir que el valor inicial del potencial gravitacional de una híper-nave es igual a cero.Solución: Sólo tenemos que utilizar la relación anterior para encontrar la suma máxima que termina en cada una de las casillas, e imprimimos el máximo de estos valores.
Código
Empezamos declarando las funciones que vamos a usar. En n leemos el número de elementos, utilizamos i para los ciclos y el arreglo p para guardar los datos.
En la función suma_max (líneas 5 a 17) obtenemos la suma máxima. Como parámetro tenemos n que es la cantidad de casillas, y como variables a i para los ciclos, max para guardar el máximo general y el arreglo m para guardar el máximo que termina en cada casilla. Empezamos inicializando la primera casilla a cero (línea 9). Para saber si utilizamos o no el valor máximo anterior, revisamos que sea positivo y en caso de que lo sea lo sumamos al valor de la casilla actual, sino, nada más tomamos el valor de esa casilla. Entre las líneas 13 y 15 buscamos la mayor de las sumas, y regresamos este valor en la línea 16.
Posibles Cambios
Podemos observar como nuestra implementación del algoritmo tiene una complejidad en espacio de O(n), debido a los dos arreglos que estamos utilizando (m y p). Es factible reducir el espacio hasta una complejidad constante tomando en cuenta lo siguiente. Los tres ciclos que usamos recorren los mismos valores (de 1 a n), y los podemos juntar en uno solo si respetamos el orden (leemos, calculamos el máximo m hasta la casilla y el máximo general). Ahora no tenemos necesidad de estar guardando la entrada, por lo suplimos el arreglo p por una variable. También nos fijamos que para calcular m[i] solo necesitamos el conocer el valor de m[i-1], por lo que cambiamos este arreglo por dos variables (valor actual y valor anterior).
Caso ejemplo
| Entrada: |
10 31 -41 59 26 -53 58 97 -93 -23 84 |
| Desarrollo: |
m[0] = 0 m[1] = max( 31, 0+ 31 )= 31 m[2] = max(-41, 31+(-41))= -10 m[3] = max( 59,-10+ 59 )= 59 m[4] = max(26, 59+ 26 )= 85 m[5] = max(-53, 85+(-53))= 32 m[6] = max( 58, 32+ 58 )= 90 m[7] = max( 97, 90+ 97 )= 187 m[8] = max(-93,187+(-93))= 94 m[9] = max(-23, 94+(-23))= 71 m[10]= max( 84, 71+ 84 )= 155 max= m[7]= 187 |
| Salida: | 187 |
Código en C
Tiempo de ejecución
| Lenguaje | Fecha | Tiempos [s] | Memoria [Kb] | |||
|---|---|---|---|---|---|---|
| Ejecución | Mejor | Mediana | Peor | |||
| Pascal | 13-Mar-2006 | 0.031 | 0.015 | 0.046 | 0.968 | 590 |
| C | 13-Mar-2006 | 0.015 | 610 | |||
Otros problemas
Valladolid:
Ural:
Introducción
