FONDO
Un problema que es simple de resolver en una dimensión a
menudo es mucho más difícil de resolver en más de una dimensión. Considere la
posibilidad de satisfacer una expresión booleana en forma normal conjuntiva en
el que cada conjunto se compone de exactamente 3 disyuntos. Este problema
(3-SAT) es NP-completo. El problema 2-SAT se resuelve de forma eficiente, sin
embargo. En contraste, algunos problemas pertenecen a la misma clase de
complejidad independientemente de la dimensionalidad del problema.
El problema
Dada una matriz de 2 dimensiones de los números enteros
positivos y negativos, encontrar el sub-rectángulo con la suma más grande. La
suma de un rectángulo es la suma de todos los elementos de ese rectángulo. En
este problema, el sub-rectángulo con la suma más grande se conoce como la
máxima sub-rectángulo. Un sub-rectángulo es cualquier sub-matriz contigua de
tamaño 1x1 o superior situado dentro de toda la gama. Como ejemplo, la máxima
sub-rectángulo de la matriz:
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
se encuentra en la esquina inferior izquierda:
9 2
-4 1
-1 8
y tiene la suma de 15.
Entrada y Salida
La entrada consiste en una matriz de NxN enteros. La entrada
comienza con un único entero positivo n en una línea por sí mismo lo que indica
el tamaño de la plaza matriz bidimensional. Esto es seguido por N^2 enteros
separados por espacios en blanco (saltos de línea y espacios). Estos N^2
enteros constituyen la matriz en orden de las filas (es decir, todos los
números de la primera fila, de izquierda a derecha, y luego todos los números
de la segunda fila, de izquierda a derecha, etc.). N puede ser tan grande como
100. Los números en la matriz estará en la gama de [-127, 127].
La salida es la suma de la máxima sub-rectángulo.
Ejemplo de entrada
4
0 -2 0 -7 -6 9 2 2
-4 1 -4 -1 1
8 0 -2
Ejemplo de salida
15
No hay comentarios:
Publicar un comentario