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