Re: [閒聊] 每日LeetCode已回收
309. Best Time to Buy and Sell Stock with Cooldown
給你股票每天的價錢，每天能買/賣/不動，問你最大收益是多少
手上只能拿一份股票，也就是買完不能再買，要等到賣掉才能執行下一次購買
賣完的隔天只能執行不動這個選項
Example 1:
Input: prices = [1,2,3,0,2]
Output: 3
Explanation: transactions = [buy, sell, cooldown, buy, sell]
Example 2:
Input: prices = [1]
Output: 0
思路:
1.DP狀態轉移類的題目，可以分成三種狀態:能賣/能買/不能買(昨天剛賣)
能賣就是手上有股票的意思，可以是原本手上就有了，也可以是能買的狀態轉移而來
所以新的值是 max(能賣, 能買-prices[i])
能買就是手上沒股票，可以是原本手上就沒有繼續不動，也可以是從不能買等一天而來
新的值是 max(能買, 不能買)
不能買就是昨天剛賣，不動的話值會被轉去能買檢查所以不用考慮
新的值是 能賣+prices[i] 也就是加上賣掉股票的錢
2.最後最大值會出現在能買/不能買之間，能賣代表手上有股票沒賣掉所以不會是最大值
能賣的初始值設成 -inf，因為一開始沒股票能賣，防止第一天的值出錯
Python code:
class Solution:
def maxProfit(self, prices: List[int]) -> int:
cansell, canbuy, cantbuy = -inf, 0, 0
for price in prices:
cansell, canbuy, cantbuy = max(cansell, canbuy-price),
max(canbuy, cantbuy), cansell+price
return max(canbuy, cantbuy)
--
蛤?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.193.79 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1671767403.A.EB9.html
推
12/23 15:38,
3年前
, 1F
12/23 15:38, 1F
→
12/23 16:06,
3年前
, 2F
12/23 16:06, 2F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 147 之 719 篇)：