Acumulados: la suma de un rectángulo con cuatro términos
UVa 108, Maximum Sum, pide el rectángulo de una matriz
n por n cuya suma es la mayor. El enunciado está en
https://vjudge.net/problem/UVA-108.
Sumar cada rectángulo celda por celda repite el mismo trabajo muchas veces.
La tabla S guarda en S[i][j] la suma de A[0..i-1][0..j-1], lo que queda
arriba y a la izquierda; con ella cualquier rectángulo cuesta cuatro
lecturas.
1. Llene la tabla de acumulados
Matriz:
La matriz A
La tabla S, con una fila y una columna de ceros
Haga clic en una casilla vacía de S y escoja su valor.
Conviene ir por filas, de izquierda a derecha: cada casilla usa la de
arriba y la de la izquierda.
2. Consulte un rectángulo
Con los cuatro valores resaltados en S, la suma es:
Verde suma, rojo resta. La esquina S[f1][c1] vuelve a
entrar porque las dos restas la quitaron dos veces.
Lo que quedó
La tabla se llena una vez, en Θ(n²). Después hay
Θ(n⁴) rectángulos y cada uno cuesta Θ(1), así que recorrerlos todos
cuesta Θ(n⁴), contra Θ(n⁶) si cada rectángulo se suma celda por celda.
Con n = 100, el tope del enunciado, son 25.502.500 rectángulos de cuatro
lecturas cada uno.
La trampa está en los bordes: sin la fila y la columna de ceros, los
rectángulos que tocan la fila 0 o la columna 0 piden S[-1], y el arreglo
tiene que declararse de tamaño (n + 1) por (n + 1). La otra está en la
entrada: los n² números no vienen fila por fila, así que se leen de corrido.
Envío en https://vjudge.net/problem/UVA-108.