Comprar y vender acciones
Dado
n números enteros que representan los precios de las acciones de tu compañía favorita, quieres determinar cuál sería el momento óptimo para comprar y vender la acción. Solo deseas comprar la acción una vez y venderla igualmente una sola vez. Por lo tanto, tu objetivo es maximizar tu ganancia (comprar barato y vender caro).Determina la ganancia máxima que puedes obtener de tu compañía favorita. En caso de que no exista forma de obtener ganancia, deberás imprimir 0 (lo que significa que no harás ninguna operación de compra o venta).
Entrada
La primera línea de la entrada contiene un solo número entero
n (1 ≤ n ≤ ).La siguiente línea contiene números separados por espacio , que representan los precios de la acción (0 ≤ ≤ 1000).
Salida
El programa debe imprimir la ganancia máxima posible que puedes obtener al comprar y vender tu acción favorita.
Ejemplos
Entrada | Salida |
5
4 2 6 8 1 | 6 |
4
8 6 4 3 | 0 |
Explicación
- Compramos cuando la acción vale 2 y la vendemos cuando vale 8
- No podemos obtener ninguna ganancia porque el precio de la acción desciende constantemente
Pista
En cada paso, puedes llevar un registro del mejor resultado posible hasta ese momento y, además, almacenar el precio más bajo que hayas visto en la acción.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB