1 題目描述

給定一個數組,其中第i個元素是第i天的股票價格。你最多可以完成兩筆交易。請計算你可以獲得的最大利潤。
注意的是,你的股票是在賣掉之前,不可以再買入。

2 解法

2.1 Recursion

一次遍歷每個股票價格,然後選擇買入或賣出,然後遞歸下去。這樣的時間複雜度是O(2^N)。

  • 沒股票:如果目前沒有股票,那麼可以選擇買入或不買入。
  • 有股票:如果目前已經有股票,那麼可以選擇賣出或不賣出。

而目前題目說,可以進行2次的transaction,基本上1次transaction就是買入和賣出,也就是2次的action,因此2次的transaction就是4次action。

從上面看到,基本上會有四種可能

  1. 買入
  2. 不買入
  3. 賣出
  4. 不賣出

我們需要幾個變數

  • idx: 當前的股票價格
  • have_stack: 是否有股票,來決定是買入還是賣出
  • count: 剩餘的交易次數

如果沒股票

1
2
3
4
5
if not have_stack:
# 這次買入(-cost),下次就只能選則賣出
do_action = -prices[idx] + helper(idx+1, not have_stack, count)
# 這次不買入,目前仍然沒有股票
not_do_action = helper(idx+1, have_stack, count)

如果有股票

1
2
3
4
5
if have_stack:
# 這次賣出(+sell),下次就只能選則買入
do_action = prices[idx] + helper(idx+1, not have_stack, count-1)
# 這次不賣出,目前仍然有股票
not_do_action = helper(idx+1, have_stack, count)

上述兩個情況的整合

1
2
3
4
sell = prices[idx]
buy = -prices[idx]
do_action = (sell if have_stack else buy) + helper(idx+1, not have_stack, count)
not_do_action = helper(idx+1, have_stack, count)

完整程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
"""
時間複雜度: O(n * 2^C)(如果 count 是變量,最壞情況下為 O(n * 2^C),其中 n 是價格列表的長度,C 是最大交易次數)
空間複雜度: O(n)(主要取決於遞歸深度)
"""
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if count == 0 or idx == len(prices):
return 0
buy = -prices[idx]
sell = prices[idx]
do_action = (sell if have_stack else buy) + helper(idx+1, not have_stack, count)
not_do_action = helper(idx+1, have_stack, count)
return max(do_action, not_do_action)
return helper(0, False, 4)

2.2 Recursion with Memoization

加入dp table,來記錄已經計算過的結果,這樣可以避免重複計算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
"""
時間複雜度: O(2^n) 每個price可以選擇買或不買
空間複雜度: O(n)
"""
class Solution:
"""transaction count = 4"""
def maxProfit(self, prices: List[int]) -> int:
def helper(idx: int, have_stack: bool, count: int) -> int:
if count == 0 or idx == len(prices):
return 0
if (idx, have_stack, count) in dp:
return dp[(idx, have_stack, count)]

buy = -prices[idx]
sell = prices[idx]

do_action = (sell if have_stack else buy) + helper(idx+1, not have_stack, count)
not_do_action = helper(idx+1, have_stack, count)
dp[(idx, have_stack, count)] = max(do_action, not_do_action)

return dp[(idx, have_stack, count)]

dp = {}
return helper(0, False, 4)

2.3 Iterative

也可以使用迭代的方式來解這個問題,這樣的時間複雜度是O(N)。
假設cost1是第一次transation買入的價格,profit1是第一次transation賣出的所獲得的利潤。
那我們會拿profit1的利潤考量進去,在買入第二次的價格,也就是cost2時,可以把profit1扣掉,這樣就可以得到第二次的所付出的成本。
然後計算profit2時,把profit2扣掉cost2,就可以得到第二次的利潤。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
"""
時間複雜度: O(n)
空間複雜度: O(1)
"""
def maxProfit2(self, prices: List[int]) -> int:
if not prices:
return 0
cost1, cost2 = float('inf'), float('inf')
profit1, profit2 = 0, 0
for p in prices:
cost1 = min(cost1, p)
profit1 = max(profit1, p - cost1)
cost2 = min(cost2, p - profit1)
profit2 = max(profit2, p - cost2)
return sell1

k次交易


如果今天是k次交易,該怎麼做呢?基本上就是要做k次的cost跟profit的更新。

1
2
3
4
5
6
7
cost1 = min(cost1, p)
profit1 = max(profit1, p - cost1)
cost2 = min(cost2, p - profit1)
profit2 = max(profit2, p - cost2)
cost3 = ...
profit3 = ...
...

如果我們使用dp去存cost跟profit,dp[i][0]表示第i次的cost,dp[i][1]表示第i次的profit。

1
2
3
4
5
6
7
8
9
10
11
"""
時間複雜度: O(n * k)
空間複雜度: O(k)
"""
def maxProfit3(self, k: int, prices: List[int]) -> int:
dp = [[float('inf'), 0] for _ in range(k)]
for p in prices:
for i in range(k):
dp[i][0] = min(dp[i][0], p - dp[i-1][1])
dp[i][1] = max(dp[i][1], p - dp[i-1][0])
return dp[k][1]

3 結論

其實一開始看到題目就是take與not take的問題,但是他難在多考慮一個變數,也就是要幾次交易,這導致同時考量兩種變數,才變得比較複雜。