1 題目描述
給定一個數組,其中第i個元素是第i天的股票價格。你最多可以完成兩筆交易。請計算你可以獲得的最大利潤。
注意的是,你的股票是在賣掉之前,不可以再買入。
2 解法
2.1 Recursion
一次遍歷每個股票價格,然後選擇買入或賣出,然後遞歸下去。這樣的時間複雜度是O(2^N)。
- 沒股票:如果目前沒有股票,那麼可以選擇買入或不買入。
- 有股票:如果目前已經有股票,那麼可以選擇賣出或不賣出。
而目前題目說,可以進行2次的transaction,基本上1次transaction就是買入和賣出,也就是2次的action,因此2次的transaction就是4次action。
從上面看到,基本上會有四種可能
- 買入
- 不買入
- 賣出
- 不賣出
我們需要幾個變數
- idx: 當前的股票價格
- have_stack: 是否有股票,來決定是買入還是賣出
- count: 剩餘的交易次數
如果沒股票
1 2 3 4 5
| if not have_stack: 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: 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的問題,但是他難在多考慮一個變數,也就是要幾次交易,這導致同時考量兩種變數,才變得比較複雜。