Cuadrado Máximo
Los Cibernéticos están implementando un nueva forma de cultivo de papa. En vez de sembrarlas en surcos, como es costumbre, las están sembrando en parcelas cuadradas de un metro de lado. El campo contiene
de estas parcelas. De cada parcela se sabe la cantidad de papas que dará al hacer la cosecha. Esta cantidad puede ser negativa porque si las papas están podridas pueden podrir otras.
Después de tanto pensar, los Cibernéticos se dieron cuenta que, dada esta forma de cultivo, la mejor manera de cosechar el campo es con un tractor especial, con sistema progamado en Java, que solo recoge un área cuadrada del campo. Calcule la mayor recolección posible utilizando el tractor solo una vez.
Entrada
Línea : Un entero positivo
.
Líneas : Cada línea contiene
enteros en el rango
.
Salida
Escribir la mayor cantidad de papas que se pueden recoger utilizando el tractor solo una vez.
Ejemplo de Entrada 1
4
2 -8 4 -6
7 1 -5 3
-9 7 6 5
8 3 2 -4Ejemplo de Salida 1
20Ejemplo de Entrada 2
3
-5 -5 -5
-5 3 -5
-5 -5 -5Ejemplo de Salida 2
3
Comments
Por que estructura de datos puedo resolver este problema?
Haces una tabla acumulativa en 2D, luego iteras por el tamaño del lado de los cuadrados, y cuando estás en un tamaño T, iteras por los cuadrados de T x T, computas la suma de cada uno usando la tabla acumulativa y vas guardando el máximo. Si la matriz es de N x N, computar la tabla acumulativa toma tiempo O(N^2), hay N posibles tamaños posibles del lado de los cuadrados, y para cada tamaño, hay O(N^2) cuadrados, por tanto haces O(N^3) operaciones, que es suficiente para este problema.