188. Best Time to Buy and Sell Stock IV

给定一个数组，数组的第i个元素代表给定股票第i天的价格

设计一个算法找出最大收益。至多完成k次交易。

注意：

不允许同时参与多个交易（也就是说，买入股票之前必须先卖出）

一次交易是指一次完整的买入和卖出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):

    # 7 star, no idea, 下面的解法来自： https://www.hrwhisper.me/leetcode-best-time-to-buy-and-sell-stock-i-ii-iii-iv/
    def maxProfit(self, k, prices):
        n = len(prices)
        if k >= (n >> 1): return self.maxProfit2(prices)
        dp = [[0 for j in range(n)] for i in range(k + 1)]

        for i in range(1, k + 1):
            maxTemp = -prices[0]
            for j in range(1, n):
                dp[i][j] = max(dp[i][j - 1], prices[j] + maxTemp)
                maxTemp = max(maxTemp, dp[i - 1][j - 1] - prices[j])
        return dp[k][n - 1]

    def maxProfit2(self, prices):
        ans = 0
        for i in range(1, len(prices)):
            if prices[i] > prices[i - 1]:
                ans += prices[i] - prices[i - 1]
        return ans