Suma Máxima 

De fondo

Un problema que es simple de resolver en una dimensión es a menudo más difícil de resolver en más de una dimensión. Consideramos satisfactorio una expresion booleana en conjunción normal, cada conjunción esta formada por 3 disyunciones. Este problema (3-SAT) es NP-completo. El problema 2-SAT es resuelto muy eficientemente. En contraste, algunos problemas pertenecen a la misma clase de complejidad a pesar de la dimensionalidad del problema.

El problema

Dado un arreglo de 2 dimensiones de enteros positivos y negativos, busca el sub-cuadro con la suma más grande. La suma de un cuadro es la suma de todos los elementos en este cuadro. En este problema el sub-cuadro con la suma más grande esta referido como el máximo sub-cuadro.Un sub-cuadro constituye algunos sub-arreglos contiguos de tamaño tex2html_wrap_inline33 o mayor localizado dentro del arreglo entero. Como un ejemplo, el máximo sub-cuadro de el arreglo:
displaymath35

esta en la esquina izquierda abajo

displaymath37

y tiene la suma de 15.

Entrada y salida

La entrada consiste de un arreglo de tamaño tex2html_wrap_inline39de enteros. La entrada comienza con un entero positivo N en una línea indicando el tamaño del arreglo de 2 dimensiones cuadrado. Esto es seguido por tex2html_wrap_inline43 enteros separados por espacios vacios(nueva líneas y espacios). Estos tex2html_wrap_inline43 enteros constituyen el arreglo en filas ordenadas (Esto es, todos los números en la primera fila, de derecha a izquierda, entonces todos los números en la segunda fila, de derecha a izquierda, etc.). N puede ser casi tan grande como 100. Los número en el arreglo estarán en el rango e [-127,127].

La salida es la suma del maximo sub-cuadro.

Ejemplo de entrada

4
0 -2 -7  0 9  2 -6  2
-4  1 -4  1 -1
8  0 -2

Ejemplo de salida

15