题目描述：

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

题目大意：

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

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

注意：

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

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

博主注：此题是在题目Best Time to Buy and Sell Stock II的基础上增加了交易次数最大值的限制条件。

解题思路：

动态规划（Dynamic Programming）

问题的实质是从长度为n的prices数组中挑选出至多2 * k个元素，组成一个交易（买卖）序列。

交易序列中的首次交易为买入，其后卖出和买入操作交替进行。

总收益为交易序列中的偶数项之和 - 奇数项之和。

dp[j]表示完成j次交易时的最大收益，转移方程如下：

dp[j] = max(dp[j], dp[j - 1] + prices[i] * [1, -1][j % 2])

当j为奇数时，交易类型为买入；

当j为偶数时，交易类型为卖出。

由于直接采用动态规划会返回Time Limit Exceeded，可以针对题目部分样例做出下面的优化：

令最大交易次数为k，数组长度为size；

则当k > size / 2时，问题可以转化为：Best Time to Buy and Sell Stock II

Python代码：

class Solution:
    # @return an integer as the maximum profit 
    def maxProfit(self, k, prices):
        size = len(prices)
        if k > size / 2:
            return self.quickSolve(size, prices)
        dp = [None] * (2 * k + 1)
        dp[0] = 0
        for i in range(size):
            for j in range(min(2 * k, i + 1) , 0 , -1):
                dp[j] = max(dp[j], dp[j - 1] + prices[i] * [1, -1][j % 2])
        return max(dp)

    def quickSolve(self, size, prices):
        sum = 0
        for x in range(size - 1):
            if prices[x + 1] > prices[x]:
                sum += prices[x + 1] - prices[x]
        return sum

内层循环的遍历方向不影响结果的正确性，下面的代码也可以通过系统测试：

class Solution:
    # @return an integer as the maximum profit 
    def maxProfit(self, k, prices):
        size = len(prices)
        if k > size / 2:
            return self.quickSolve(size, prices)
        dp = [None] * (2 * k + 1)
        dp[0] = 0
        for i in range(size):
            for j in range(1, min(2 * k, i + 1) + 1):
                dp[j] = max(dp[j], dp[j - 1] + prices[i] * [1, -1][j % 2])
        return dp[2 * k]

    def quickSolve(self, size, prices):
        sum = 0
        for x in range(size - 1):
            if prices[x + 1] > prices[x]:
                sum += prices[x + 1] - prices[x]
        return sum

 

本文链接：http://bookshadow.com/weblog/2015/02/18/leetcode-best-time-to-buy-and-sell-stock-iv/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码