← Volver a los ejercicios

El mejor tramo: sigue o se reinicia

UVa 507, Jill Rides Again, da la calificación de cada calle de una ruta y pide el tramo de calles seguidas con la mayor suma. Si dos tramos empatan en suma gana el más largo, y si también empatan en largo gana el que empieza antes. El enunciado está en https://vjudge.net/problem/UVA-507. Probar todos los tramos cuesta Θ(n²) sumas; un recorrido basta si en cada posición se decide si el tramo que viene se alarga o se abre uno nuevo.

1. El arreglo

Ejemplos:
Propio:
Las tres rutas son los casos de prueba del enunciado. En el último ejemplo varios tramos suman lo mismo.

2. Decida en cada posición

suma e ini son del tramo que termina en i; mejor, mi y mf son del mejor tramo visto.
tramo actual mejor tramo la posición i

iA[i]tramosumainimejormi..mfel mejor