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]))
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/103791.html
標籤：Python
上一篇：120三角形最小路徑之和