Python|你真“贪心”之买股票

引言

当今社会很多人都喜欢选择一种投资方式—买股票。股票波动比较大，自然风险也很高，当然如果方向选择正确，获益也是比较高的。那么用贪心算法解决买股票的题再合适不过了。因为大家都是想低价买入，高价卖出，收益自然就很多，这一点足以体现贪心。那么贪心算法是对局部的最优解，自然就不是整体的最优解，关键在于贪心的策略的不同，策略的过程不会影响以后的状态，只与当前状态有关。

问题描述

给定一个数组prices，其中prices[i]是一支给定股票第i天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例1：

输入:prices = [7,1,5,3,6,4]

输出：7

示例2：

输入：prices = [1,2,3,4,5]

输出：4

解决方案

其实本道题目有两种解决方法，其一是动态规划，其二就是贪心算法；在这里我们将讲解贪心算法，贪心算法是这道题的特殊解法。结合示例1来看，第一天股票价格太高不买入，第二天价格低买入，第三天股票价格升高，卖出股票，这笔交易收入5-1=4，第四天的时候买入，第五天又卖出，则获得利润6-3=3，总获得利润为7。结合下图一起看。

现在我们结合示例2看，又会发现差别。由于前几天价格都低，但是又不能连续买入，因为这样属于同时参与多笔交易。

像示例1和2是两种不同的类型，对于示例一我们需要找出升区间，然后计算峰值与最低值的价格差，即[1,5]和[3,6]两个区段都是再升，那么他们的差值相加就是最终的收益。示例二是一个升区间，例[a,b,c,d,e]，假设这里面的元素大小依次增加，即e最大，a最小，那么最大收益必然是e-a，e-a=(e-d)+(d-c)+(c-b)+(b-a)。所以在写的时候就要判断前后两天的价格差是否大于0，若大于0就要添加到收益里面。

结语

解决此题可能还有很多方法，我用了贪心算法，在编写程序前一定要读懂题目的意思，不要一拿到题目就写代码，先对题目分析，看看该如何去解决，每个示例的不同点在什么地方。

实习编辑：王晓姣

作者：赵玉琴

稿件来源：深度学习与文旅应用实验室（DLETA）