1 題目描述

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

2 解法

2.1 Recursion

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

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

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

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

買入
不買入
賣出
不賣出

我們需要幾個變數

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

如果沒股票

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)

如果有股票

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)

上述兩個情況的整合

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)

完整程式碼

"""
時間複雜度: 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，來記錄已經計算過的結果，這樣可以避免重複計算。

"""
時間複雜度: 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，就可以得到第二次的利潤。

"""
時間複雜度: 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的更新。

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。

"""
時間複雜度: 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]