leetcode122 买卖股票的最佳时机 python

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目:给定一个数组，它表示了一只股票的价格浮动，第i个元素代表的是股票第i天的价格.设计一个函数，计算出该股票的最大收益，注意，可以多次买入卖出，但下一次买入必须是在本次持有股票卖出之后.比如[1，7，2，3，6，7，6，7]，最大收益为9，第1天买入，第2天卖出，然后第3天买入，第6天卖出，第7天买入，第8天卖出.

分析:该题目的难点在于可以多次买入和卖出.

#1 找极值

股票交易取得良好收益的方法是低价买入，高价卖出，并且由于该股票可以多次买入卖出，所以应该在极小值点买入，极大值点卖出.如下图所示的股票价格折线图，点1，点3，点7均为极小值点，点2，点6，点8均为极大值点，它们分别对应的就是买入和卖出的时间.因此，只要找到数组的极小值点和极大值点就可以解决该问题.在数学中，寻找极值的方法是求导，但此处只是一个有限长度且无规律的数组，按照极值的定义寻找即可，即邻域内的最大值和最小值，在数组值持续增大时，停止增大的点就是极大值，在数组值持续减小，停止减小的点就是极小值.代码如下.

class Solution:
def maxProfit(self， prices):
"""
:type prices: List[int]
:rtype: int
"""
i=0
earned=0
buy=0
while i<len(prices)-1:
while i<len(prices)-1 and prices[i+1]<=prices[i]:#极小值
i+=1
buy=i
while i<len(prices)-1 and prices[i+1]>=prices[i]:#极大值
i+=1
sell=i
earned+=(prices[sell]-prices[buy])
return earned

代码注意两点:(1) 因为买入日期应当在卖出日期之前，因此先进行极小值的判断，再进行极大值的判断;(2)买入时间要初始化，因为可能会存在[1，2，3，4，5]这样的情况，这时程序无法找出极小值1.

#2 极值进阶版

其实题目并不要求输出买入和卖出的日期，只要求输出最后受益，所以其实我们并不需要找到极小值和极大值的点，只需要知道它们的差值，而b-a=(b-c)+(c-a)，换句话说，可以通过极大值和极小值之间中间值，通过价格上涨的累加，算出最后的价格差值.比如上面的折线图，[1，7，2，3，6，7，6，7]，当第3天买入后，第4天价格上涨1，第5天价格上涨3，第6天价格上涨1并停止上涨，股票卖出，那么从买入到卖出的收益为1+3+1=7-2=5.代码如下。

class Solution:
def maxProfit(self， prices):
"""
:type prices: List[int]
:rtype: int
"""
earned=0
if len(prices)<=1:
return earned
for i in range(len(prices)-1):
if prices[i+1]>prices[i]:
earned+=(price[i+1]-prices[i])
return earned

#3 暴力求解

暴力求解是最简单粗暴的方法，但关键仍然在于股票可以多次买入卖出，不能简单的将买入时间和卖出时间枚举一遍，代码如下。

class Solution:
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
def partProfit(start,prices):
if start==len(prices)-1:
return 0
maxprofit=0
for i in range(start,len(prices)-1):
maxi=0
for j in range(i+1,len(prices)):
if prices[j]>prices[i]:
profit=partProfit(j+1,prices)+prices[j]-prices[i]
if profit>maxi:
maxi=profit
if maxi>maxprofit:
maxprofit=maxi
return maxprofit
return partProfit*0,prices)