我被伤害了，在看到那几行代码的时候，我的眼眶开始发热，我的脑子开始不清醒，我是谁，我为什么会在这儿，我为什么这么菜。思考了大概十几分钟，我折服了。

我的公众号-菜的一批欢迎关注

好吧，记录一下伤害我的动态规划问题。前天刚学习了动态规划问题，也分析了最长递增子串问题，但并没有进行深入的刷题理解，今天就给了我暴击。

---

正文

上题目：买卖股票的最佳时机

力扣121买卖股票的最佳时机

0. 依然暴力破解先

在穷举解决的时候，这个问题变得如此简单。

• 第一天买入，第二天卖出，计算差价
• 第一天买入，第三天卖出，计算差价

.....

• 第倒数第二天买入，第倒数第一天卖出，计算差价
  +计算所有差价中最大的即可

上代码:

def maxProfit(self, prices) -> int:
      if len(prices) == 0 or len(prices) == 1:
            return 0
      max = 0
      for i in range(len(prices)):
          for j in range(i + 1, len(prices)):
               if prices[j] - prices[i] > max:
                    max = prices[j] - prices[i]
        return max

结果不出所料：

超时，又是满满一整页的测试数据

很容易分析，在如此大数据量的情况下，双层循环的时间复杂度，加上本身python的效率比较低，超时是必然的，来优化吧。

1.思考篇

1.1 是不是可以去重

在观察测试数据的时候发现有很多重复的数据，于是想到了用集合去重，但是因为题目要求必须在卖出股票前买入股票，也就是说序列的先后顺序不能改变。如果采用了集合又因为集合是无序的，就可能导致顺序改变。放弃。

1.2 是不是可以进行排序

假如我们将整个数列排序，然后从后往前找大值，再从前往后找小值，只要找到一组满足，在原来的序列中大值排在小值后就可以。
但是仔细一分析，因为找的是一组，最坏时间复杂度依然是，而且加上排序使用的时间，再加上存储排序后占用的空间，不合算，甚至更糟。放弃。

1.3是不是可以进行动态规划

我越来越觉得这个题目有最长递增序列长度的影子，只要从某一天开始找，找一个最长的递增序列即可。在本题中不太好实施，那不妨想一想动态规划的思想。无后效性，我突然意识到问题没有那么复杂，一步一步来揭开神秘的面纱。

• 我们现在就在第N天，我们今天就试着卖一下股票
• 如何让我们今天卖出去的股票收益最好？抄底，从之前的日子里选取买入的价格最低的那天买进就好了
• 重复这个过程，我们每天都要卖，每天更新最大的收益

上代码：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) == 0 or len(prices) == 1:
            return 0
        max = 0
        for i in range(1, len(prices)):
            if max <= (prices[i] - min(prices[:i])):
                max = prices[i] - min(prices[:i])
        return max

看结果：

这也太慢了吧

看来我们还没有找到真正的解决方法
仔细分析：我们每次都要找一个最小值，这个找最小值的过程依然是的复杂度，而且综合起来本算法的最坏时间复杂度也来到了，没有从根本上改变。但是为什么不是超时了，我们也可以清除的看到，暴力法是从前往后算（从今天买入，找卖出的价格最大的日子），本算法是从后往前算（从今天买出，找买入的价格最低的日子）。其实本质上并未解决问题。

2.重新思考动态规划

我们是不是漏了什么，或者把什么东西想复杂了。
动态规划讲究的无后效性是指我们可以充分利用之前已经算好的东西。假如今天卖出的就是最大的收益，那么如果该收益还要变多，那只能是从这个收益上增加，包括买入的最小价格也是如此。一旦我们找到一个最小的买入价格，我们是不是可以记录下来，下次遇上新的一天，我们就不需要再去找的最小值，只要和当前最小值比较就好了，我的天，动态规划的思想淋漓尽致。 记录以前已经生成的值，一步一步向后移动，每一步移动只需要将记录的值与该步产生的值进行比较，判断是否要更新。

这样一想，代码自然有了：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) == 0 or len(prices) == 1:
            return 0
        maxs = 0
        mins = prices[0]
        for i in range(1, len(prices)):
            maxs = max(maxs, prices[i] - mins)
            mins = min(mins, prices[i])
        return maxs

结果很舒适：

到此这个问题已经解决了，我们不妨再多思考思考
为什么一下在从6s到60ms这么大的差距，原因就在于，我们减少了很大一部分的找最小值的过程，而是从前往后走的时候走一步，记录一步，更新一步。这样一来，只要从头走到尾基本上结果也就确定了，时间复杂度为 O(n)
哇哦，神奇，美妙。

经此一役，实在是佩服至极，算法中蕴含的乐趣大概就是这样吧，继续努力~~~