原題

假設(shè)你有一個(gè)數(shù)組，它的第i個(gè)元素是一支給定的股票在第i天的價(jià)格。
設(shè)計(jì)一個(gè)算法來(lái)找到最大的利潤(rùn)。你最多可以完成 k 筆交易。

給定價(jià)格 = [4,4,6,1,1,4,2,5], 且 k = 2, 返回 6.

你不可以同時(shí)參與多筆交易(你必須在再次購(gòu)買(mǎi)前出售掉之前的股票)

解題思路

• 動(dòng)態(tài)規(guī)劃，循環(huán)引用的狀態(tài)數(shù)組(local/global數(shù)組)
• mustSell[i][k] 表示前i天，至多進(jìn)行k次交易，第i天必須sell的最大獲益
• globalbest[i][k] 表示前i天，至多進(jìn)行k次交易，第i天可以不sell的最大獲益
• 狀態(tài)轉(zhuǎn)移方程

mustSell[i][k] = max(globalBest[i - 1][k - 1] + profit, mustSell[i - 1][k] + profit)
globalBest[i][k] = max(globalBest[i - 1][k], mustSell[i][k])

舉例：

• 交易4次第5天必須賣(mài)出的最大值等于，四天之前交易3次賣(mài)出的最大值加上第4天買(mǎi)第5天賣(mài)的利潤(rùn)與交易4次第四天必須賣(mài)出的最大值加上第四天買(mǎi)第五天買(mǎi)的利潤(rùn)(相當(dāng)于第四天賣(mài)了又買(mǎi)，還是4次交易)，兩者的較大值
• 交易4次前5天必須賣(mài)出的最大值等于，交易4次前4天賣(mài)出的最大值與交易4次第5天賣(mài)出的最大值，兩者的較大值

完整代碼

class Solution(object):
    def maxProfit(self, k, prices):
        """
        :type k: int
        :type prices: List[int]
        :rtype: int
        """
        if k == 0:
            return 0
            
        if k >= len(prices) / 2:
            profit = 0
            for i in range(1, len(prices)):
                diff = prices[i] - prices[i - 1]
                if diff > 0:
                    profit += diff
            return profit
            
        n = len(prices)
        mustSell = [[0 for i in range(k + 1)] for i in range(n + 1)]
        globalBest = [[0 for i in range(k + 1)] for i in range(n + 1)]
        
        for k in range(k + 1):
            mustSell[0][k] = globalBest[0][k] = 0
            
        for i in range(1, n):
            profit = prices[i] - prices[i - 1]
            mustSell[i][0] = 0
            for k in range(1, k + 1):
                mustSell[i][k] = max(globalBest[i - 1][k - 1] + profit, mustSell[i - 1][k] + profit)
                globalBest[i][k] = max(globalBest[i - 1][k], mustSell[i][k])
                
        return globalBest[n - 1][k]