股票买卖

股票买卖Leetcode上现在有6道题目，分别如下：

根据是否限制买卖次数可以分为两类

一类是限制买卖次数的，如 121，123，188

另外一类是不限制买卖次数的，如122，309， 714

不限制买卖次数

不限制买卖次数，就是说可以买卖任意多的次数（但实际上受限于prices的长度！）。122题目可以看做是该类的基础版，然后309、714分别从两个角度强化了题目难度。

先将基础版，该题目只要定义两个变量buy,sell，然后顺着prices数组往后遍历。这两个变量分别代表如下含义：

buy: 持有股票状态下的最大收益。刚开始持有状态的收益肯定是 -prices[0]，因为新买入的嘛

sell: 不持有股票状态下的最大收益。刚开始不持有状态的收益肯定是0，因为还没进行过交易

状态转移图如下：

遍历prices数组中的price for price in prices, 然后分别做如下更新：+

买入（持有股票）状态不断做如下更新 buy = max(buy, sell-price) 解释：要么不进行买入，要么进行买入。如果进行买入，那肯定是用之前一天的不持有的最大收益sell来当做本金，再减去当天股票的价钱。

卖出（不持有股票）状态不断做如下更新 sell = max(sell, buy+price) 解释：要么不进行卖出，要么进行卖出。如果进行卖出，肯定是利用前一天买入的最大收益加上当天卖出去赚回来的钱。

当然可以定义两个长度等同prices的数组 buy_dp = [0 for _ in range(len(price))], sell_dp = [0 for _ in range(len(price))]. 但真的有必要吗？显然没有。因为每个状态仅和之前一个状态以及当前状态的上一个数值相关，所以完全没必要定义数组，仅有两个变量就足够。

122 完整代码如下：


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        buy = -prices[0]
        sell = 0

        for price in prices:
            buy = max(sell-price, buy)
            sell = max(sell, buy+price)

        return sell

理解了上述基础题目，再来看强化版 309题目。

该题目定义了一个新概念冷冻期，其实就是限制了买入的时机，不能在卖出的第二天进行买入。那不能在卖出的第二天进行买入，那我就在卖出的第三天或者之后进行买入好了。

怎么理解呢？之前买入的状态转移方程为 buy = max(buy, sell - price) ，sell-price其实就可能是在卖出的第二天进行买入。那要怎么区分是否真的是在第二天买入的呢？我再引入一个变量lastSell，该变量在当天sell变量更新前进行赋值 lastSell = sell。这样在下一天就能保证lastSell 存放的肯定不是前一天的sell了，当然此buy = max(buy, lastSell - price)

此时有个问题，因为lastSell存放的是当前之前2天的sell, 所以prices数组必须要从第3天开始遍历，这样buy,sell 初始化也必须初始化到第二天。

309完整代码如下


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) <= 1:
            return 0
        # 初始化 
        buy = - min(prices[0:2])            # 当前持有的最大收益
        sell = max(0, prices[1]-prices[0])  # 当前不持有的最大收益
        lastSell = 0                        # 前一天不持有的最大收益
        
        # 从第二天开始买入
        for i in range(2, len(prices)):
            buy = max(buy, lastSell-prices[i])
            # 在更新sell 前更新一下lastSell
            lastSell = sell
            sell = max(sell, buy+prices[i])

        return sell

最后再来看强化版 714题目.这道题是引入了手续费，且手续费是在每次交易时都需要交付。这样就简单了很多，我们只需要在122题目的基础上，卖出的时候再把手续费剪掉就可、

714完整代码如下


class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        buy = -prices[0]
        sell = 0
        for price in prices:
            buy = max(buy, sell-price)
            sell = max(sell, buy+price-fee) # 卖出的时候 把手续费减掉

        return sell

限制买卖次数

限制买卖次数的题目其实只是不限制买卖次数的特例。比如121题目，限制只能买一次，那么我更新buy的时候就不能采用 buy = max(buy, sell-price) 了，因为 sell-buy 其实是利用上一次卖出之后的收益来减去当前股票价钱，来和buy比较看是否需要再次买入的。既然我们不需要再次买入了，那么buy就应该这样更新 buy = max(buy, 0-price) 这样buy永远都是以最低价格，sell 更新规则不变，依旧是sell = max(sell, buy+price)

121 完整代码如下


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        buy = -prices[0]
        sell = 0
        for price in prices:
            buy = max(buy, 0-price)
            sell = max(sell, buy+price)
        return sell

123 题目在121的基础上，限制买卖次数最多为 2 次，这样就需要定义四个变量了，分别为 fstBuy, fstSell, sedBuy, sedSell. 含义和之前一样

123 完整代码如下


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        fstBuy, scdBuy = -prices[0], -prices[0]
        fstSell, scdSell = 0, 0
        for price in prices:
            fstBuy = max(-price, fstBuy)
            fstSell = max(fstSell, fstBuy+price)

            scdBuy = max(scdBuy, fstSell-price)
            scdSell = max(scdSell, scdBuy + price)

        return scdSell

188题目是在123 的基础上扩展了买卖次数，限定买卖次数为 k 次，这样只需要定义两个长度为(k+1)的数组即可

188 完整代码如下：


class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        if len(prices) <= 1 :
            return 0
        buy = [-prices[0]] * (k+1)
        sell = [0] * (k+1)

        for price in prices:
            for i in range(1, k+1, 1):
                buy[i] = max(buy[i], sell[i-1]-price)
                sell[i] = max(sell[i], buy[i]+price)
                
        return sell[-1]