[LeetCode]188 买卖股票的最佳时机IV

题目描述

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例1

输入: [2,4,1], k = 2
输出: 2
解释: 在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

示例2

输入: [3,2,6,5,0,3], k = 2
输出: 7
解释: 在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
     随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

思路

  • 今天第x次买入状态的最大收入=max(昨天第x次买入状态的最大收入+0【今天不卖】,昨天第x-1次卖出状态的最大收入+今天的股票价格【今天买入】)
  • 今天第x次卖出状态的最大收入=max(昨天第x次卖出状态的最大收入-0【今天不买】,昨天第x-1次买入状态的最大收入-今天的股票价格【今天卖出】)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def maxProfit(self, k, prices):
        """
        :type k: int
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) <= 1 or k <= 0:
            return 0
        max_profit = 0
        if len(prices) <= 2*k + 1:
            for i in range(1, len(prices)):
                if prices[i]-prices[i-1] > 0:
                    max_profit += prices[i]-prices[i-1]
            return max_profit
        buy, sell = [-2**31]*k, [0]*k
        for price in prices:
            for i in range(k):
                buy[i] = max(buy[i], -price) if i == 0 else max(buy[i], sell[i-1]-price)
                sell[i] = max(sell[i], price+buy[i])
        return sell[-1]