leetcode188. Best Time to Buy and Sell Stock IV(買賣股票的最佳時機 IV)

題目要求

給定一個數組，它的第 i 個元素是一支給定的股票在第 i 天的價格。

設計一個算法來計算你所能擷取的最大利潤。你最多可以完成 k 筆交易。

注意: 你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

解題要求

來了來了！！ 正常股票四連的最後一道，首先仔細想想看這四道題的内容有什麼差別和聯系。

補充 股票四連合集，看了不虧，沒看後悔！！：

NO.1 leetcode 121 Best Time to Buy and Sell Stock（買賣股票的最佳時機）

NO.2 leetcode122. Best Time to Buy and Sell Stock II (買賣股票的最佳時機 II)

NO.3 leetcode123. Best Time to Buy and Sell Stock III（ 買賣股票的最佳時機 III）

NO.4 leetcode188. Best Time to Buy and Sell Stock IV(買賣股票的最佳時機 IV)

第一道題的要求是，我們隻賣買一次；

第二題是無限次數的買賣；

第三題是隻能買賣兩次；

題是買賣k次。

注意啦！！ 那我們在做第四題的時候，是不是就相當于考慮了前面的三種情況？第一題實際是K=1,第二題實際是K=無窮，第三題是K=2.

本題由于 k 的大小可以非常大, 一定要先判斷 k 的大小,然後分情況讨論。

如果超過範圍 （n/2）, 則要轉換為無限次的股票買賣, 否則會導緻爆棧。無窮次數的話就和第二題是一樣的，我們比較前後兩次的價格，如果內插補點為正就加入利潤。

如果在可以接受的範圍内（小于n/2），那麼我們就仿照的第一，三題的樣子，通過Kadane’s算法來進行計算，分别比較每次的買入價格和賣出價格。如果符合要求我們就進行更新。直到K次完畢！

難點是：K的大小時影響計算的，是以我們要根據K的大小進行分情況讨論。

主要代碼python

class Solution(object):
    def maxProfit(self, k, prices):
        def maxProfitKInf(prices):
            max_profit = 0
            for i in xrange(1, len(prices)):
                if prices[i] > prices[i-1]:
                    max_profit += prices[i] - prices[i-1]
            return max_profit

        if k == 0 or not prices:
            return 0
        
        n = len(prices)

        # k is considered as infinite here
        if k >= n / 2:
            return maxProfitKInf(prices)

       
        buy, sell = [float('inf')] * (k+1), [0] * (k+1)
        for i in xrange(n):
            for j in xrange(1, k+1):
                buy[j] = min(buy[j], prices[i]-sell[j-1])
                sell[j] = max(sell[j], prices[i]-buy[j])
        return sell[k]
           

原題連結：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv