常梦网 常梦网

【leetcode】best time to buy and sell stocks(i, ii, iii, iv, v) - 程序媛Sophia

时间: 2024-02-29  热度:

i.只允许一次交易

ii.允许多次购买

iii 至多允许两次购买

    class Solution(object):        def maxProfit(self, prices):if len(prices) < 2:    return 0n = len(prices)        prePro = [0] * n        postPro = [0] * n        curMin = prices[0]        for i in range(1, n):if curMin > prices[i]:    curMin = prices[i]prePro[i] = max(prePro[i - 1], prices[i] - curMin)        curMax = prices[n - 1]        for i in range(n - 2, 0, -1):if curMax < prices[i]:    curMax = prices[i]postPro[i] = max(postPro[i + 1], curMax - prices[i])        maxPro = 0        for i in range(n):maxPro = max(maxPro, prePro[i] + postPro[i])        return maxPro

iv:ii和iii的延伸,至多k次购买

事实上iii是其中k = 2的情况。而ii是k >= len(prices)的情况。
这道题的思路很自然地能想到用dp。但是一个状态方程是有问题的。一开始自己并没有意识到,于是犯错了。
以下摘自http://liangjiabin.com/blog/2015/04/leetcode-best-time-to-buy-and-sell-stock.html

分析:特殊动态规划法。传统的动态规划我们会这样想,到第i天时进行j次交易的最大收益,要么等于到第i-1天时进行j次交易的最大收益(第i天价格低于第i-1天的价格),要么等于到第i-1天时进行j-1次交易,然后第i天进行一次交易(第i天价格高于第i-1天价格时)。于是得到动规方程如下(其中diff = prices[i] – prices[i – 1]):
profiti = max(profiti – 1, profiti – 1 + diff)
看起来很有道理,但其实不对,为什么不对呢?因为diff是第i天和第i-1天的差额收益,如果第i-1天当天本身也有交易呢(也就是说第i-1天刚卖出了股票,然后又买入等到第i天再卖出),那么这两次交易就可以合为一次交易,这样profiti – 1 + diff实际上只进行了j-1次交易,而不是最多可以的j次,这样得到的最大收益就小了。

那么怎样计算第i天进行交易的情况的最大收益,才会避免少计算一次交易呢?我们用一个局部最优解和全局最有解表示到第i天进行j次的收益,这就是该动态规划的特殊之处。

用locali表示到达第i天时,最多进行j次交易的局部最优解;用globali表示到达第i天时,最多进行j次的全局最优解。它们二者的关系如下(其中diff = prices[i] – prices[i – 1]):

locali = max(globali – 1 , locali – 1 + diff)
globali = max(globali – 1, locali)
locali和globali的区别是:locali意味着在第i天一定有交易(卖出)发生,当第i天的价格高于第i-1天(即diff > 0)时,那么可以把这次交易(第i-1天买入第i天卖出)跟第i-1天的交易(卖出)合并为一次交易,即locali=locali-1+diff;当第i天的价格不高于第i-1天(即diff<=0)时,那么locali=globali-1+diff,而由于diff<=0,所以可写成locali=globali-1。globali就是我们所求的前i天最多进行k次交易的最大收益,可分为两种情况:如果第i天没有交易(卖出),那么globali=globali-1;如果第i天有交易(卖出),那么globali=locali。

class Solution(object):

    def maxProfit1(self, prices):        """        :type prices: List[int]        :rtype: int        """        if len(prices) < 2:return 0        maxPro = 0        for i in range(1, len(prices)):if prices[i] > prices[i - 1]:    maxPro += prices[i] - prices[i - 1]        return maxPro    def maxProfit(self, k, prices):        n = len(prices)        if n < 2:return 0        if k >= n:return self.maxProfit1(prices)        profit1 = [[0] * (k + 1)] * n        profit2 = [[0] * (k + 1)] * n        diff = [0] * n        for i in range(1, n):diff[i] = prices[i] - prices[i - 1]for j in range(1, k + 1):    profit1[i][j] = max(profit2[i - 1][j - 1], profit1[i - 1][j] + diff[i])    profit2[i][j] = max(profit1[i][j], profit2[i - 1][j])        return profit2[n - 1][k]

v:with cooldown:

class Solution(object):

    def maxProfit(self, prices):        if len(prices) < 2:return 0        n = len(prices)        sellPro = [0] * n        buyPro = [0] * n        sellPro[0] = 0        buyPro[0] = 0 - prices[0]        sellPro[1] = max(prices[1] - prices[0], 0)        buyPro[1] = max(-prices[0], -prices[1])    for i in range(2, n):sellPro[i] = max(buyPro[i - 1] + prices[i], sellPro[i - 1])buyPro[i] = max(buyPro[i - 1], sellPro[i - 2] - prices[i])    return sellPro[-1]

相关阅读