from typing import List
# 這道題是個簡單的動態規劃的題目，
# 每天可以分為四種情況，
# 1，不持有股票，買入，2，不持有股票，不買入，3，持有股票，不賣出，4，持有股票，賣出
# 那我們就可以根據四種情況來列動態方程，
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# 如果天數小于2，那么利潤只能是0
if len(prices) < 2:return 0
# 這里定義一個思維陣列，用來存放每天，每一種情況的利潤
now_prices = [[0,0,0,0] for i in range(len(prices))]
now_prices[0][0] = -prices[0] # 不持有股票，買入
now_prices[0][1] = 0 # 不持有股票不買入，
# 下邊這兩種情況在第一天是不可能的，因此我們可以把它們定義為無窮小，
now_prices[0][2] = float('-inf')# 持有股票賣出，
now_prices[0][3] = float('-inf') # 持有股票，不賣出，
for i in range(1,len(prices)):
# 注意看下邊的動態轉移方程，
# 今天不持有買入的話，那么昨天只能是，持有賣出或者不持有不買入，我們計算利潤，把花出去的減少，
now_prices[i][0] = max(now_prices[i - 1][1],now_prices[i - 1][2]) - prices[i]
# 今天不持有，不買入，那么昨天就是持有賣出或者不持有不買入，
now_prices[i][1] = max(now_prices[i - 1][1],now_prices[i - 1][2])
now_prices[i][2] = max(now_prices[i - 1][0],now_prices[i - 1][3]) + prices[i]
now_prices[i][3] = max(now_prices[i - 1][0],now_prices[i - 1][3])
# 回傳最后一天四種情況的最大值、
return max(now_prices[-1])
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/206663.html
標籤：其他
上一篇：技術點1：HTML