Una sola operación de bolsa
La misión
Problema
Recibes una lista con los precios diarios de una acción, donde la posición i guarda el precio del día i. Puedes comprar un día y vender un día estrictamente posterior, como máximo una vez. Devuelve la mayor ganancia que puede dar esa única operación. Si ningún día posterior paga más que uno anterior, devuelve 0, porque lo mejor es no operar.
Ejemplos
Input: prices = [8, 3, 6, 1, 9, 4]
Output: 8
Por qué: compras el día 3 a 1 y vendes el día 4 a 9
Input: prices = [7, 5, 4, 2]
Output: 0
Por qué: los precios solo bajan, así que cualquier operación perdería dinero
Input: prices = [5]
Output: 0
Por qué: caso límite: con un solo día no queda un día posterior para vender
Pistas
0 / 3
Comparar cada día de compra con cada día de venta funciona, pero repite mucho trabajo. Pregúntate qué podría recordar una sola pasada de izquierda a derecha.
Mientras avanzas en el tiempo, del pasado solo importan dos datos: el precio más bajo visto hasta ahora y la mejor ganancia encontrada hasta ahora.
Recorre los días una vez. En cada día, primero calcula la venta de hoy contra el precio más bajo anterior y guárdala si supera tu récord; después baja el mínimo acumulado si hoy es más barato que todo lo anterior.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(1)
Solución
Recorre los precios una vez llevando el precio mínimo visto hasta ahora. Vender el día actual vale el precio de hoy menos ese mínimo, así que comparar ese valor con la mejor ganancia hasta ahora mantiene la respuesta al día. Actualizar el mínimo después de calcular la venta garantiza que el día de compra siempre sea estrictamente anterior al de venta. El tiempo es O(n) con una sola pasada y el espacio es O(1), ya que solo se guardan dos números.
def max_trade_profit(prices):
best = 0 # best profit found so far
cheapest = float("inf") # lowest price seen up to today
for p in prices:
# a sale today is only worth as much as the cheapest earlier buy
best = max(best, p - cheapest)
cheapest = min(cheapest, p)
return best
print(max_trade_profit([8, 3, 6, 1, 9, 4])) # -> 8
print(max_trade_profit([7, 5, 4, 2])) # -> 0
print(max_trade_profit([5])) # -> 0¿Lo que te frena es la idea y no el código? Algoritmo de Kadane lo explica.