martes, 3 de marzo de 2015

enunciado 108 suma maxima

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