Problema 4
Suma Máxima
suma.pas, suma.c, suma.cpp
Problema
Dado un arreglo cuadrangular de números enteros, encontrar el subrectángulo cuya suma de sus entradas sea máximo, al cual llamaremos Subrectángulo Máximo. Las dimensiones de los subrectángulo pueden ser de 1×1. Ejemplo: Considera el siguiente arreglo rectangular:
| 0 | -2 | -7 | 0 |
| 9 | 2 | -6 | 2 |
| -4 | 1 | -4 | 1 |
| -1 | 8 | 0 | 2 |
El subrectángulo máximo es el formado por la dos primeras columnas y los tres últimos renglones y su suma es 15:
| 9 | 2 |
| -4 | 1 |
| -1 | 8 |
Recuerda que un cuadrado es también un rectángulo.
Entrada
La entrada consiste en un arreglo de enteros. El primer renglón en un entero positivo n (1 ≤ n ≤ 100) que indica la dimensión del cuadrado. Los siguientes renglones estarán enteros separados por un espacio. En cada renglón se pondrán una cantidad indeterminada de enteros. Los números estarán entre –127 y 127.
Salida
La suma del máximo subrectángulo.
Ejemplo
| entrada | salida |
| 4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 |
15 |
| Concurso: | ICPC - 1 Concurso Interno de la Universidad Bonaterra. 18/Mayo/2001 |
| Tomado de: | UVa Online Judge - 108 |
| Ayuda: | entradas, salidas, sugerencias |
| Soluciones: | suma.pas, suma.c, suma.cpp |