← Volver a los ejercicios

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

Verde suma, rojo resta. La esquina S[f1][c1] vuelve a entrar porque las dos restas la quitaron dos veces.