[LeetCode]Best Time to Buy and Sell Stock IV

题目描述:

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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

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

Pingbacks已关闭。

评论
  1. Maples7 Maples7 发布于 2015年3月21日 16:37 #

    DP时最大值一定是 dp[2*k] 而不必求 max(dp)。

  2. 在线疯狂 在线疯狂 发布于 2015年3月21日 16:51 #

    没错!已经修改。

  3. newtt newtt 发布于 2015年3月22日 09:00 #

    第二种方法随不影响结果的正确性,但是逻辑上是错误的,因为它实际上的意义是允许了同一天有又买又卖

  4. 在线疯狂 在线疯狂 发布于 2015年3月22日 11:09 #

    最初提交的时候使用的是第2段代码,我在思考有没有反例。如果可以通过所有测试样例,或许也是一种可取的方法,但是dp数组所代表的含义就与解法1不同了。

  5. 王薇薇 王薇薇 发布于 2015年3月29日 23:33 #

    [1, -1][j % 2] 请问是什么意思?

  6. 在线疯狂 在线疯狂 发布于 2015年3月30日 16:12 #

    等价于-1的j次幂。
    j为奇数时值为-1,j为偶数时值为1

张贴您的评论