← Volver a los ejercicios

La mayor diferencia en un solo recorrido

UVa 11078, Open Credit System, da las notas de n estudiantes ordenados del más antiguo al más nuevo y pide el mayor valor de A[i] - A[j] con i < j. El enunciado está en https://vjudge.net/problem/UVA-11078. Probar todas las parejas cuesta dos ciclos; basta uno si, al llegar a cada j, ya se sabe cuál es el mayor A[i] que quedó atrás.

1. El arreglo

Ejemplos:
Propio:
Los tres primeros ejemplos son los casos de prueba del enunciado, cuyas respuestas son 80, 3 y -1.

2. Avance j y prediga

Un recorrido
Dos ciclos
ya recorrido la casilla j el máximo que se resta

máximo de A[0..j-1]

mejor al terminar la vuelta

jA[j]máximo de A[0..j-1]candidatamejor

3. Lo que cuesta cada versión

Comparaciones de la línea 4 y la línea 7 del recorrido, contra las de la línea 4 de los dos ciclos, para este mismo arreglo.

un recorrido
dos ciclos
Con n números, los dos ciclos comparan n(n - 1)/2 parejas y el recorrido hace 2(n - 1). Con cuatro números o menos el recorrido no compara menos; desde cinco la distancia crece con cada número que se agrega.