月饼的最佳买卖时机

作者丨牛牛码特

来源丨牛牛码特（ID：niuniu_mart）

大家好，我是牛牛，中秋节快到了，今天就来分享一道和月饼有关的基础算法题，提前祝大家中秋快乐！

01故事起源

中秋节快到了，牛牛买了几盒公司月饼，过了几天，再打开内网一看，月饼的价格已经从公司的发售价78，涨到了150。短短几天，就翻了倍，这勾起了牛牛的好奇心，开始关注🥮价格。  

盯了两天，发现价格每天都有波动，牛牛算是明白了，这鹅厂的月饼也变成了抢手货，有黄牛在中间捣腾，作为一个合格的程序员，当然联想到了自己的业务——这要是放在计算机里，黄牛的最佳买入卖出时机如何实现？

02输入输出我们以月饼每天的售价为输入，输出最大利润：
输入[7，1，5，3，6，4]
输出

5

上例中，黄牛在第1天（月饼价格=1）的时候买入，在第4天（月饼价格=6）的时候卖出，可以获得最大利润=6-1=5。

03花式炒饼

老规矩，我们还是由简入难，看看有哪些方法解决这个问题。

暴力法

简单来说，我们可以找到每一天和它之前天的差值，其中，差值最大的一组就是我们的最佳买卖时机。
在实际运行中，我们需要把每种可能性都算出来，最后找到差值最大的那组。

func maxProfit(prices []int) int { var result int for i := 1; i < len(prices); i++ { for j := 0; j < i; j++ { result = max(result, prices[i] - prices[j]) } } return result}
这种方式虽然直截了当，但是时间复杂度是O(N^2)，如果数据量比较多的时候，耗时会很长。在算法题中，可能会超时，一般只是作为基础解法，理清思路。

贪心算法

暴力法容易想到，但是效率太低。
想要利润最大，肯定是希望在最低点买入。我们就从一开始的时候，不断更新最低点，最低点和卖出点差值越大则利润越大。

如图所示，从第0天开始，0是最低点，7块钱。到第1天，最低点只有1块钱，后续始终没有比1块钱更低的，所以第1天就是买入点。寻找到后续价格与第1天差值最大的那天，就是卖出点。

func maxProfit(prices []int) int { var minPrice = prices[0] var result int for i := 1; i < len(prices); i++ { minPrice = min(minPrice, prices[i]) diff := prices[i] - minPrice result = max(result, diff) } return result}

动态规划

我们刚才是以贪心的思路去看待问题，这道题用动态规划也是可以的。因为我们求解最佳的买卖点，其实可以看作最大递增子序列。
我们以数组dp表示以某天为卖点的最大获利。dp[i]的值取决于它前一天dp[i-1]和第i天的价格：假设如果第i天的价格减第i-1天的价格为diff，dp[i]就是dp[i-1] + diff，dp[i]不能为负，如果小于0，则令其等于0。

func maxProfit(prices []int) int { var dp = make([]int, len(prices)) var result int for i := 1; i < len(prices); i++ { diff := prices[i] - prices[i-1] dp[i] = max(dp[i-1] + diff, 0) if dp[i] > result { result = dp[i] } } return result}
04月饼复盘暴力法简单粗暴，心智成本低，但是执行效率也低。用它来帮助理清思路即可。
贪心算法符合生活常识，就像名字所说一样，求取当前的最值。最后的动态规划则是以迭代递推的思路解决问题。

这三种算法在算法题中都是非常常规和重要的，大多数算法题其实都可以用这三种思路去套，一开始我们可能不太熟悉，多多应用到不同题目，自然就会手到擒来了。
最后，祝大家都能在中秋吃到自己最喜欢的月饼！

点分享

点点赞

点在看