欢迎光临
我们一直在努力

算法题买卖股票的最佳时机(买卖股票的最佳时机)

欢迎来到算法的世界,现在我们在第一层:初级算法。

开始我们的旅途吧!

算法题买卖股票的最佳时机

题目

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

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

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

示例

输入: [7,1,5,3,6,4]输出: 7解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

输入: [1,2,3,4,5]输出: 4解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。 因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。

输入: [7,6,4,3,1]输出: 0解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

题解

这道题属于一道求最优解的题目,这类题目需要经过一系列的步骤,每个步骤又有不同的选择,而贪心算法,则是在每一步做出在当时看起来是最优的选择,得到局部的最优解,最终导致全局的最优解。

这道题的贪心流程,应该是下面这样:

在当天,我们要判断下昨天与今天的股价差,如果有上升,也就是今天比昨天高,就应该把正数的差额作为当前最优解,计入总利润中,一步一步往下走,走到最后一天,则得到了最终的最大利润。

这道题目中的每一步就是: “今天的股价 – 昨天的股价”。

每一步的结果包括了:正数、负数、零。

每一步的最优解,根据题目来看的话,也就是最大的意思,也就是贪心所有的正数差。

但这个算法不代表真正的交易,只代表了计算过程,它可以得到最优解,就以示例中的[1,2,3,4,5]为例,我们在1、2、3、4、5的时候,根据这个算法流程,我们应该是

计算prices[i]-prices[i-1]的差是不是正数,是的话则计入总利润,也就是

总利润 = (prices[1]-prices[0]) + (prices[2]-prices[1]) + (prices[3]-prices[2]) + (prices[4]-prices[3]) = prices[4] – prices[0]。

可以看出,算法的流程上如果看做真正的交易的话,买进第一天的,第二天卖出,然后又买入第二天的,第三天卖出,直到最后一天,但是按照规则,不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票),但这个流程的结果又可以看做且等价为:在第一天买入,在最后一天卖出,能得到最大的利润(prices[4] – prices[0]),也就是真正的交易过程。

可能有朋友就有疑虑了,为什么能这么笃定,贪心算法得到的解就一定是最优解呢,我们可以这样来想一下:

贪心算法根据每步的最优解得到结果,在这道题目中,每步的最优解也就是正数,之所以每一步的结果加起来会是最优解,我们可以假设,贪心算法得到的最终结果并不是一个全局最优解,那么就存在其他方式可以得到最优解,但是贪心算法是每次都得到最优也就是正数,那么其他算法,如果他拿的不是正数,而是零,那此时最终结果肯定比贪心得到的值小,如果它拿到的是正数,那最终结果就等于贪心得到的值,如果它拿到的是负数,那最终结果就肯定比贪心得到的值小。

也就是说,除了贪心算法,找不到能得到更大的结果的算法,所以贪心算法可以通过局部最优得到全局最优解。

下面附上贪心算法的java代码图

算法题买卖股票的最佳时机

JAVA代码图

赞(0) 打赏
未经允许不得转载:股票知识平台 » 算法题买卖股票的最佳时机(买卖股票的最佳时机)
分享到: 更多 (0)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏