Tema
Supongamos que el precio de una acción se almacena en la matriz en orden, ¿cuánto es el beneficio máximo de comprar y vender la acción una vez?
Ejemplo 1
Entrar: [7, 1, 5, 3, 6, 4]
Salida: 5
Explicación: Comprar en el segundo día (precio de la acción = 1), venderlo en el día 5 (precio de la acción = 6), beneficio máximo = 6-1 = 5 .
Tenga en cuenta que los beneficios no pueden ser 7-1 = 6, porque los precios de venta deben ser mayores que los precios de compra.
Ejemplo 2:
Entrar: [7, 6, 4, 3, 1]
Salida: 0
Explicación: En este caso, no hay ninguna transacción que completar, por lo que el beneficio máximo es 0.
Pensar
Pregunte al máximo beneficio DP [i] en el día I, es el valor máximo en estos dos casos: uno se vende antes del día I, el otro se vende en la primera i.
Si se vende antes que yo, entonces el beneficio máximo DP [i] del día i es el máximo beneficio DP [I-1] en el primer día;
Si se vende en el día i, el máximo beneficio DP [i] del día i es el precio mínimo del primer día i-1.
Ecuación de transferencia dinámica:
dp[i] = max(dp[i-1],prices[i]-min(prices[0:i]))
Debido a que el suscriptor de la matriz Price comienza a partir de 0, el precio del día i-th es realmente precios [i -1].
Código
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
if n==0 or n==1: return 0
dp = [0,0]
min_value = prices[0]
for i in range(2,n+1):
min_value = min(min_value,prices[i-2])
res = max(dp[i-1],prices[i-1]-min_value)
dp.append(res)
return dp[n]
la complejidad
Complejidad de tiempo O (N)
Complejidad espacial O (N)
