UVa 507, Jill Rides Again, pide el tramo de calles
consecutivas con la mayor suma. El enunciado está en
https://vjudge.net/problem/UVA-507.
La solución recorre el arreglo una vez con dos acumuladores: suma, que
sigue o vuelve a 0, y mejor. Aquí se sigue solo el valor del tramo; las
paradas se guardan junto a mejor con dos variables más. El invariante de
mejor no se deja demostrar sin el de suma.
1. La especificación y la predicción
Para abreviar, S(s, e) = A[s] + … + A[e − 1] es la
suma del tramo A[s..e), y S(s, s) = 0 es la del tramo vacío.
Entrada: un arreglo A[0..N) de enteros, N ≥ 1.
Salida: máx {S(s, e) : 0 ≤ s ≤ e ≤ N}.
Arreglo:
Los tres últimos son las rutas del caso de ejemplo del
enunciado. Con mejor = 0 el programa imprime que la ruta no tiene tramo
bueno.
¿Qué devuelve mejorTramo(A)?
2. Ejecute y mire
Paso 0 de 0
Las casillas azules son A[0..i), las que el ciclo ya
leyó. Cada vez que la ejecución pasa por la línea 5, el while evalúa
su condición y la terna (i, suma, mejor) queda en la tabla.
3. La traza por estados
Chequeo
i
suma
mejor
¿Qué se repite?
Una fila en rojo es el chequeo donde falla la fórmula
que eligió en la tarjeta 4. La columna de la derecha se llena cuando
acierte los tres invariantes.
4. Los invariantes
Busque lo que se cumple en todas las filas,
incluida la primera y la última, escrito en términos de N, i y A.
¿Entre qué valores se mueve i en los chequeos? (I₀)
¿Qué guarda suma? (I₁)
¿Y mejor? (I₂)
5. La demostración
Encuentre primero los
tres invariantes en la tarjeta 4. El teorema a demostrar:
Teorema 1. Los invariantes I₀, I₁ e I₂ se cumplen.
Inicialización: tras las líneas 1 a 4, ¿qué vale (i, suma, mejor)?
Para I₀: 0 ≤ 0 ≤ N. ✓ Para I₁: el único s
con 0 ≤ s ≤ 0 es s = 0, y S(0, 0) = 0 = suma. ✓ Para I₂: el único
tramo con 0 ≤ s ≤ e ≤ 0 es el vacío, S(0, 0) = 0 = mejor. ✓
Estabilidad. Se toma una vuelta con i = t,
0 ≤ t < N, y se asumen I₀, I₁ e I₂ en t. Los tramos de A[0..t + 1)
son los de A[0..t) más los que terminan en t. ¿Cuál es el mejor tramo no
vacío que termina en t?
Todo tramo no vacío que termina en t es
A[s..t) seguido de A[t], con 0 ≤ s ≤ t. Por I₁ en t,
máx {S(s, t + 1) : 0 ≤ s ≤ t} = máx {S(s, t) : 0 ≤ s ≤ t} + A[t] =
suma + A[t], que es lo que deja la línea 6. Sin I₁ no hay forma de
obtener ese valor: mejor no dice dónde termina su tramo.
La línea 10 pone suma en 0 cuando es negativa.
¿Qué tramo representa ese 0?
Sea s' = suma + A[t], el valor tras la línea 6.
I₂ en t + 1. Las líneas 7 y 8 dejan mejor' = máx (mejor, s'). Los
tramos de A[0..t + 1) son los de A[0..t), cuyo máximo es mejor por I₂ en
t, y los no vacíos que terminan en t, cuyo máximo es s' por el paso
anterior. Luego mejor' = máx {S(s, e) : 0 ≤ s ≤ e ≤ t + 1}. ✓
I₁ en t + 1. Las líneas 9 y 10 dejan suma' = máx (s', 0). Los
tramos que terminan en t con 0 ≤ s ≤ t + 1 son los no vacíos, de máximo
s', y el vacío S(t + 1, t + 1) = 0. Luego
suma' = máx {S(s, t + 1) : 0 ≤ s ≤ t + 1}. ✓
I₀ en t + 1. La línea 11 deja i = t + 1, y de 0 ≤ t < N sale
1 ≤ t + 1 ≤ N, luego 0 ≤ t + 1 ≤ N. ✓
La estabilidad de I₂ usó I₁ en el paso anterior; la de I₁ solo usó I₁.
I₁ es la pieza que hace demostrable a I₂.
Terminación: ¿con qué valor de i termina el ciclo?
El ciclo termina porque i crece de 1 en 1 e I₀ lo
acota por N. Al salir, la condición i < N es falsa, o sea i ≥ N; con
i ≤ N de I₀ queda i = N. Sustituyendo en I₂:
mejor = máx {S(s, e) : 0 ≤ s ≤ e ≤ N}, que es la poscondición. ∎
Teorema 2. La invocación mejorTramo(A) sobre
cualquier arreglo con N ≥ 1 devuelve máx {S(s, e) : 0 ≤ s ≤ e ≤ N}, que
es 0 exactamente cuando ningún tramo tiene suma positiva.
Demostración: por el Teorema 1 los invariantes se cumplen; la
terminación deja i = N, y sustituir ese valor en I₂ da la poscondición. ∎
El recorrido hace N vueltas de costo constante: O(N), contra los
N(N + 1)/2 tramos no vacíos que revisa la solución que prueba cada
inicio y cada fin.
6. Para llevarse
Sin solución aquí. La solución completa guarda
también inicio, el comienzo del tramo de suma, y mi, mj, los extremos del
tramo de mejor, y ante un empate se queda con el tramo más largo. Escriba
un invariante para inicio que relacione suma con S(inicio, i), y otro para
mi y mj que diga cuál de los tramos de suma mejor elige.