La suma máxima de una forma rectangular sub-array

Question

Dada una matriz de números con valores reales, A[1..n,1..n], deseo de encontrar el sub-conjunto

B = A[i..j,s..t]

con 1 <= i <= j <= n, y 1 <= s <= t <= n

de tal manera que la suma de los números en B está maximizada. ¿Es posible resolver esto usando programación dinámica? Hablé con uno de los profesores de quirófano de la Universidad de Aarhus, y él no sabía cómo hacerlo, y dijo que tenía dificultades para ver cómo podía tener la calidad óptima de la subestructura.

¿Pero es posible? Si es así, ¿cómo? Si no, ¿por qué?

que ya sé de un algoritmo que se ejecuta en O(n^3) tiempo, reduciéndola a n(n+1)/2 subproblemas de complejidad O(n), pero que parece que es un poco lento. Sé que un algoritmo óptimo funcionaría en el tiempo Omega(n), pero espero que la programación dinámica se pueda usar para hacerlo funcionar en el tiempo O(n^2).

pregunta original resumen

añadí esta sección, porque sentía que algunas personas han malinterpretado el punto de mi pregunta. La pregunta original fue:

1. ¿Es posible utilizar la programación dinámica para resolver el problema anterior en O(n^2) vez? Si es así, ¿cómo? Si no, ¿por qué no?

preguntas adicionales:

I añadido una nueva preguntas aquí. Más podría agregarse más tarde:

1. Para utilizar la programación dinámica, necesito hacer uso de soluciones para resolver fácilmente los subproblemas (o el punto es irrelevante). La estructura del problema es tal, que si tomamos un subarreglo B = A[1..m,1..m] de A[1..n,1..n] donde m < n, entonces la solución óptima para la matriz B es como mucho buena en A, trivialmente, ya que la misma solución es factible en A. Para utilizar la programación dinámica, es razonable preguntarse: ¿Cuál es la relación entre el subcampo óptimo de A[1..i,1..i] y el subcampo óptimo de A[1..i+1,1..i+1]?

Answer 1

De The Algorithmist, si usted tiene un n por n matriz, lo mejor que puede hacer es O (n^3):

• En primer lugar, calcular la suma de prefijo vertical para todas las columnas (una junta (n^2) algoritmo).
• En segundo lugar, suponga que la subarranque máxima estará entre la fila a y la fila b, ambas incluidas. Solo hay O (n^2) a, b pares tales que a < b. Prueba cada uno de ellos.
• Como ya tenemos la suma del prefijo vertical para todas las columnas, la suma de los elementos en arr [a..b] [c] para la columna c se puede calcular en O (1) tiempo. Esto nos permite imaginar cada suma de columna como si fuera un elemento único de una matriz unidimensional en todas las columnas (matriz unidimensional con una fila yn columnas).
• Hay un algoritmo O (n) para calcular la matriz secundaria máxima para una matriz unidimensional, conocida como Algoritmo de Kadane.
• Al aplicar el algoritmo de Kadane dentro de cada combinación ayb se obtiene la complejidad total de O (n3).

Dado que tiene una matriz n por 2, puede bajarla a O (n^2). La clave, como la anterior, es usar Kadane's algorithm

Answer 2

Una optimización posiblemente útil sería omitir la comprobación de los pares a, b cuando se puede calcular que es imposible que el puntaje supere la mejor corriente.

Por ejemplo, una forma de hacer esto sería:

1. algoritmo de Run Kadane en cada fila (n repeticiones de O (n) algoritmo = O (n^2)) y almacene el valor máximo en una matriz M.
2. Calcular la suma de prefijo vertical de la matriz M en O (n) tiempo
3. Ahora para cada a, b par podemos usar nuestra suma de prefijo vertical para obtener un límite superior para la suma que se puede obtener de este emparejamiento y omita la prueba si es menor que nuestro mejor valor actual.

Esto probablemente funcione mejor si también ejecuta el algoritmo de Kadane en la matriz M y prueba primero el par a, b resultante.

En el mejor de los casos (por ejemplo, la imagen contiene un fondo negro y un rectángulo blanco en el interior) encontrará la respuesta en O (n^2), pero para entradas más complicadas todavía tomará O (n^3)

ADVERTENCIA: En la práctica, este truco probablemente sólo ayudar a un conjunto muy pequeño de los insumos, el costo de ralentizar la mayoría ...

EDIT: alguna explicación adicional:

Para fila i, M [i] contiene el mayor valor que se puede obtener de cualquier rectángulo de altura 1 de la forma A [i..i, x..y].

Definimos una nueva matriz P [i] (llamada la suma del prefijo vertical en la descripción anterior).

P[0]=0 
P[i+1]=M[i]+P[i] 

Para una determinada elección de filas s y t podemos obtener una estimación rápida del valor más alto que se puede conseguir de cualquier rectángulo de la forma A [s..t, x..y] calculando sum (M [i] para i en rango (s, t + 1)). En realidad, esto nos da el valor de una forma algo así como:

...   Row s 
.... 
....... 
    ....  Row t 

forma tomando la mejor altura del rectángulo 1 de cada fila entre s y t.

La matriz P [i] es útil porque P [i] = suma (M [j] para j en el rango (i)), por lo que podemos calcular la suma (M [i] para i en rango (s, t + 1)) = P [t + 1] -P [s] en O (1) tiempo.