121.买卖股票的最佳时机


from typing import List
class Solution:
# 错误的思路,会超时。
def maxProfit1(self, prices: List[int]) -> int:
if len(prices) <= 1:return 0 # 小于等于一天没法交易买和卖
# 进行双重遍历
for index1 in range(len(prices)):
# 最大收益
max_prices = 0
for index2 in range(index1 + 1,len(prices)):
# 第二重遍历,判断index1的最大收益
if prices[index1] < prices[index2]:
if prices[index2] - prices[index1] > max_prices:
max_prices = prices[index2] - prices[index1]
# 求出最大收益,
prices[index1] = max_prices
# 返回最大收益
return max(prices)
# 动态规划的解法
def maxProfit(self, prices: List[int]) -> int:
if len(prices) <= 1:return 0 # 小于等于一天没法交易买和卖
dp = [0 for _ in range(len(prices))]
min_price = prices[0] #设置最低的价格,总是在价格最低的时候买入
# 进行遍历,每一天的情况
for index in range(1,len(prices)):
# 判断今天的价格是否比最小值小,是的话,就改变最小值
if min_price > prices[index]:
min_price = prices[index]
# 今天如果卖出的话,股票的时候是否比前一天的收益要大。
# 今天的收益肯定是要比前几天的收益要大。,
dp[index] = max(prices[index] - min_price,dp[index - 1])
print(dp)
return dp[-1]
A = Solution()
print(A.maxProfit([7,1,5,3,6,4]))
print(A.maxProfit([7,6,4,3,1]))

作者:月为暮,发布于:2020/06/30
原文:https://www.cnblogs.com/cong12586/p/13215319.html