← Volver a los ejercicios

El mejor tramo: dos invariantes que se sostienen

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

Chequeoisumamejor¿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.