情境描述:
股票信息包括每天交易的最高价、最低价以及开盘价。设计算法,根据给定的股价走势信息,决定买入和卖出策略,保证交易获得的利润最大化
方法一:暴力枚举法
# 定义股票开盘价数组s=[10,4,8,7,9,6,2,5,3]maxProfit=0buyDay=0sellDay=0# 遍历所有可能组合for i in range(len(s)-1):for j in range(i+1,len(s)):if s[j]-s[i]>maxProfit:maxProfit=s[j]-s[i]buyDay=iselDay=jprint("应该在第{0}天买入,在第{1}天卖出,最大利润为{2}".format(buyDay+1,selDay+1,maxProfit))
输出:
应该在第2天买入,在第5天卖出,最大利润为5
分析:这个算法的时间复杂度为n^2,显然不是最优解
方法二:分治法
思路:在前半部分找到最小值,在后半部分找到最大值,只需要一个循环即可
def findMaxProfit(S):# 返回值格式:买入日期,卖出日期,最大利润if len(S)<2:return [0,0,0]if len(S)==2:if (S[1]-S[0])>0:return [0,1,S[1]-S[0]]else:return [0,0,0]left=findMaxProfit(S[0:int(len(S)/2)])right=findMaxProfit(S[int(len(S)/2):int(len(S))])finnalResult=leftif (right[2]>left[2]):right[0]+=int(len(S)/2)right[1]+=int(len(S)/2)finnalResualt=right# 遍历最低买入日期和最高卖出日期lowPrice=S[0]highestPrice=S[int(len(S)/2)]buyDay=0selDay=int(len(S)/2)# 遍历最低买入日期for i in range(0,int(len(S)/2)):if (S[i]<lowPrice):buyDay=ilowPrice=S[i]# 遍历最高卖出日期for j in range(int(len(S)/2),int(len(S))):if (S[j]>highestPrice):selDay=jhighestPrice=S[j]# 计算最大利润if (highestPrice-lowPrice>finnalResult[2]):finnalResult[0]=buyDayfinnalResult[1]=selDayfinnalResult[2]=highestPrice-lowPricereturn finnalResultS=[1,2,9,4,5,6,7,10]maxProfit=findMaxProfit(S)print("在第{0}天买入,在第{1}天卖出,可以获得最大利润{2}:".format(maxProfit[0]+1,maxProfit[1]+1,maxProfit[2]))
输出:
在第1天买入,在第8天卖出,可以获得最大利润9:
分析:这种方法使用递归来实现,首先将问题分解为两个部分,在两个小的部分分别遍历最小值和最大值,然后再回传差值即可。 时间复杂度为nlg(n)
方法三:最优解法
S=[1,2,9,4,5,6,7,10]minPrice=S[0]buyDay=0selDay=0profit=0i=0for i in range(len(S)):# 遍历最小买入值if (S[i]<minPrice):minPrice=S[i]buyDay=i# 遍历最大收益值if (S[i]-minPrice>profit):profit=S[i]-minPriceselDay=iprint("在第{0}天买入,在第{1}天卖出,可以获得最大利润{2}:".format(buyDay+1,selDay+1,profit))
输出:
在第1天买入,在第8天卖出,可以获得最大利润9:
分析:这种方法只需要遍历一遍数组,时间复杂度为n