Tarea 4 de Análisis y Diseño de Algoritmos
Trimestre 2014 Invierno
Entrega: 3 de febrero de 2014 a las 22:00.
Imagine que observa el precio de un artículo de alta necesidad
durante N días consecutivos, es decir, el precio del artículo es
P[I] el día I (1 <= I <= N). Suponga que desea comprar ese
artículo un día C para venderlo en una día posterior V. ¿Cómo debe
escoger estos días para maximizar la ganancia G de la operación?
Escriba un programa llamado gananciaZZ
(donde ZZ es la clave
de dos dígitos asignada por el profesor) que lea un entero N y los N
precios enteros P[1], ..., P[N] y que calcule el día de compra C, el
día de venta V y la ganancia máxima correspondiente G. Por ejemplo
si N = 3 y P = [9, 1, 5] entonces debe comprar el día C = 2 y vender
el día V = 3 para ganar G = 4. Puede suponer que 2 <= N <=
100,000 y que 1 <= P[I] <= 2,000,000,000 para 1 <= I <=
N.
Ejemplo de entrada
|
Ejemplo de salida
|
3
9 1 5
|
2 3 4
|
Pista: Existe un algoritmo cuadrático muy simple y será
demasiado lento. Use la técnica de divide y vencerás para un
algoritmo O(N log N).
Notas: Sus programas no deben leer ni escribir nada
adicional a lo que se indica en el enunciado. El tiempo
de ejecución de sus algoritmos será considerado como parte de la
evaluación.