¿Cómo puedo encontrar la suma máxima de una subsecuencia usando la programación dinámica?

Question

Estoy volviendo a leer el Manual de diseño de algoritmos de Skiena para ponerme al día con algunas cosas que he olvidado desde la escuela, y estoy un poco desconcertado por sus descripciones de Programación Dinámica. Lo busqué en Wikipedia y en otros sitios, y si bien todas las descripciones tienen sentido, tengo problemas para resolver problemas específicos por mi cuenta. Actualmente, estoy trabajando en el problema 3-5 del libro de Skiena. (Dada una matriz de n números reales, encuentre la suma máxima en cualquier subvector contiguo de la entrada.) Tengo una solución O (n^2), tal como se describe en this answer. Pero estoy atrapado en la solución O (N) usando programación dinámica. No está claro para mí cuál debe ser la relación de recurrencia.

veo que las subsecuencias forman un conjunto de sumas, así:

S = {a, b, c, d}

a a+b a+b+c a+b+c+d 
    b  b+c  b+c+d 
      c  c+d 
        d 

Lo que no entiendo es cómo elegir cuál es el más grande en tiempo lineal. Intenté hacer cosas como realizar un seguimiento de la suma más grande hasta el momento, y si el valor actual es positivo, agréguelo a la suma. Pero cuando tienes secuencias más grandes, esto se vuelve problemático porque puede haber tramos de números negativos que disminuirían la suma, pero un gran número positivo posterior puede hacer que vuelva a ser el máximo.

También me acuerdo de tablas de área sumadas. Puede calcular todas las sumas usando solo las sumas acumulativas: a, a + b, a + b + c, a + b + c + d, etc. (Por ejemplo, si necesita b + c, es simplemente (a + b + c) - (a).) Pero no ve una forma O (N) de obtenerlo.

¿Alguien puede explicarme qué es la solución de programación dinámica O (N) para este problema en particular? Siento que casi lo entiendo, pero me estoy perdiendo algo.

Answer 1

Debe take a look to this pdf de vuelta en la escuela en http://castle.eiu.edu aquí está:

La explicación de la siguiente pseudocódigo también se int pdf.

Answer 2

Hay una solución como, primero ordenar la matriz en al parte de la memoria auxiliar, luego aplicar el método Sub-secuencia más larga común a la matriz original y la matriz ordenada, con suma (no la longitud) de sub- común secuencia en las 2 matrices como la entrada a la tabla (Memoization). Esto también puede resolver el problema

El tiempo total de ejecución es O (nlogn) + O (n^2) => O (n^2) El espacio es O (n) + O (n^2) => O (n^2)

Esta no es una buena solución cuando la memoria entra en escena. Esto es solo para dar una idea de cómo los problemas se pueden reducir entre sí.

Answer 3

Mi comprensión de DP es sobre "hacer una mesa". De hecho, el significado original de "programación" en DP es simplemente hacer tablas.

La clave es averiguar qué poner en la tabla, o términos modernos: qué estado seguir, o cuál es la clave/valor de vértice en DAG (ignore estos términos si le suenan extraños).

¿Qué hay de elegir dp[i] mesa que es la suma más grande que termina en el índice i de la matriz, por ejemplo, siendo la matriz [5, 15, -30, 10]

La segunda clave importante es "óptima subestructura", que es 'asumir' dp[i-1] ya se almacena la suma más grande de sub-secuencias que termina en el índice i-1, es por eso que el único paso en i es decidir si se debe incluir a[i] en la sub-secuencia o no

dp[i] = max(dp[i-1], dp[i-1] + a[i]) 

El primer término en max es "no incluir un [i]", el segundo término es "incluir un [i]". Aviso, si no incluimos a[i], la suma más grande hasta el momento sigue siendo dp[i-1], que proviene del argumento "subestructura óptima".

Así que todo el programa se parece a esto (en Python):

a = [5,15,-30,10] 

dp = [0]*len(a) 
dp[0] = max(0,a[0]) # include a[0] or not 

for i in range(1,len(a)): 
    dp[i] = max(dp[i-1], dp[i-1]+a[i]) # for sub-sequence, choose to add or not  


print(dp, max(dp)) 

El resultado: mayor suma de sub-secuencia debe ser el elemento más grande de dp mesa, después de i iterar a través de la matriz a. Pero mira de cerca dp, contiene toda la información.

Dado que solo pasa por elementos en la matriz a una vez, es un algoritmo O (n).

Este problema parece tonto, porque mientras a[i] sea positivo, siempre deberíamos incluirlo en la subsecuencia, ya que solo aumentará la suma. Esta intuición coincide con el código

dp[i] = max(dp[i-1], dp[i-1] + a[i]) 

Así que la max. la suma del problema de la subsecuencia es fácil, y no necesita DP en absoluto. Simplemente,

sum = 0 
for v in a: 
    if v >0 
     sum += v 

Sin embargo, ¿qué pasa con la suma más grande del problema "continuous sub-array". Todo lo que tenemos que cambiar es sólo una sola línea de código

dp[i] = max(dp[i-1]+a[i], a[i])  

El primer término es "incluyen a [i] continua en el sub-matriz", el segundo término es decidir para iniciar una nueva sub- array, iniciando un [i].

En este caso, dp[i] es el máximo. sum. subsubray continuo que termina con index-i.

Esto es ciertamente mejor que un enfoque ingenuo O (n^2) * O (n), a for j in range(0,i): dentro del i-loop y sum todas las sub-matrices posibles.

Una pequeña advertencia, porque el modo dp[0] está establecido, si todos los elementos en a son negativos, no seleccionaremos ninguno. Así que para la suma max continua sub-matriz, cambiamos que a

dp[0] = a[0]