一魚多吃 用狀態機和DP解 有冷卻期的股票作多最大獲利 Leetcode #309

Yiorgos Ntrahas on Unsplash

題目敘述

題目會給我們一個輸入陣列prices分別代表不同交易日的股票價格，問我們在帶有冷卻條件的情況下，不限制交易次數，請問作多的最大獲利是多少?

冷卻條件的定義:

賣出股票的下一天，不能買入股票。

也就是說第i天賣出股票，最快要在i+2天才可以選擇買入股票。

詳細的題目可在這裡看到

測試範例

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

約束條件

Constraints:

• 1 <= prices.length <= 5000
• 0 <= prices[i] <= 1000

演算法 DP + 狀態機

我們可以模仿 股票作多最大獲利系列題 第二題的作法，用狀態機State machine列出每一天有可能的情況，搭配DP動態規劃中的狀態轉移關係式和初始條件解出來。

通過題意的分析和測試範例，每一天可以分為三種狀態

Cool-down 冷卻日:

前一天可能來自冷卻日 或者 股票賣出日。

Hold 持有日:

前一天可能來自冷卻日，接著買入並持有股票；或者前一天也可能來自 持有日，代表原本就已經持有股票，繼續持有股票。

Sell 賣出日:

前一天只有可能來自持有日，原本持有股票，選擇在今天賣出，接著下一天會強迫進入冷卻日。

初始狀態，也就是初始化時，有一個細節要留意，股票不可能無中生有，免費獲得利潤，所以Hold要記得初始化成 負無窮大。

最後，最大獲利一定來自於手上持有現金部位，也就是說，一定來自於賣出日Sell或者冷卻日Cool-down，兩者取其大，取Maximal value就是最大獲利，也是最終回傳的答案。

image

程式碼

class Solution:
　def maxProfit(self, prices: List[int]) -> int:
　　
		# initialization
　　cool_down, sell, hold = 0, 0, -float('inf')
　　
　　for stock_price_of_Day_i in prices:
　　　
　　　prev_cool_down, prev_sell, prev_hold = cool_down, sell, hold
　　　
　　　# Max profit of cooldown on Day i comes from either cool down of Day_i-1, or sell out of Day_i-1 and today Day_i is cooling day
　　　cool_down = max(prev_cool_down, prev_sell)
　　　
　　　# Max profit of sell on Day_i comes from hold of Day_i-1 and sell on Day_i
　　　sell = prev_hold + stock_price_of_Day_i
　　　
　　　# Max profit of hold on Day_i comes from either hold of Day_i-1, or cool down on Day_i-1 and buy on Day_i
　　　hold = max(prev_hold, prev_cool_down - stock_price_of_Day_i)
　　
　　
　　# The action of final trading day must be either sell or cool down
　　return max(sell, cool_down)

複雜度分析

時間複雜度:

O( n )

從左到右，掃描過每個交易日，迴圈長度和原本的陣列一樣長。

空間複雜度:

O( 1 )

所用到的是狀態機儲存狀態的變數、和迴圈迭代的索引，都是固定尺寸的臨時變數，皆為常數級別O(1)。

Reference:

[1] Python/Go/Java/JS/C++ O(n) by DP and state machine. [w/ Visualization] - Best Time to Buy and Sell Stock with Cooldown - LeetCode