python買賣股票的最佳時機（基于貪心/蠻力算法）

更新時間：2019年07月05日 14:59:10 作者：劍峰隨心

這篇文章主要介紹了python買賣股票的最佳時機（基于貪心/蠻力算法）,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下

開始刷leetcode算法題今天做的是“買賣股票的最佳時機”

題目要求

給定一個數(shù)組，它的第 i 個元素是一支給定股票第 i 天的價格。

設(shè)計一個算法來計算你所能獲取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。

注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。

看到這個題目最初的想法是蠻力法

通過兩層循環(huán) 不斷計算不同天之間的利潤及利潤和

下面上代碼

class Solution(object):
  def maxProfit(self, prices):
    """
    :type prices: List[int]
    :rtype: int
    """

    self.allbuy1 = []  #單次買賣的差值數(shù)組 （可能為負(fù)）
    self.allbuy2 = []  #所有可能買賣的利潤數(shù)組 （可能為負(fù)）
               # allbuy1和allbuy2的區(qū)別為一個是單次買賣 一個是多次買賣和
    self.curbuy(prices,0,0) #prices 為價格表 0：初始 0：
    #print(self.allbuy1)
    #print(self.allbuy2)
    return self.picBigest(self.allbuy2)
  def buyticket(self,prilist,a,b):    #list:放入的價格數(shù)組 a:上一次買入的價格 b:今天賣出的價格
    return prilist[b] -prilist[a]  #返回 賺取得價格

  def curbuy(self,plist,x,result): #plist：價格數(shù)組 x:當(dāng)天的數(shù)組坐標(biāo) result: 利潤
    obj=result           #固定上一次的價格 保存為上一個遞歸
    lens=len(plist)        #天數(shù)
    for i in range(x,lens-1):
      for j in range(i+1,lens):
        temp=self.buyticket(plist,i, j)
        self.allbuy1.append(temp)
        self.allbuy2.append(temp)   #單次利潤放入數(shù)組
        result = obj + temp   #將之前的利潤加上今天的利潤
        if(x>=2):       #如果買入是第2+1天以后 則可以加上之前的利潤
          self.allbuy2.append(result) #多次買賣利潤放入數(shù)組
        self.curbuy(plist,j+1,result)  #遞歸 j+1:賣出的后一天 result:利潤

  def picBigest(self,reslist): 
    big=0
    for i in reslist:
      if (i>big):
        big=i
    print(big)
    return big

if __name__ == '__main__':
    test=Solution()
    prices = [5,7,3,8] # 輸入的每日股票數(shù)組
    test.maxProfit(prices)

分析：

這個代碼理解起來簡單就是將所有可能都放入數(shù)組中找出最大一個可能

將這個代碼提交時顯示超出時間限制確實如果輸入的數(shù)組長度非常大時計算量巨大出現(xiàn)錯誤

——————————————————————————————————————————————————————————————————————————————

更換思路：利用貪心算法解決此事

首先介紹一下貪心算法：對問題只對當(dāng)前情況進行最優(yōu)解處理，之后發(fā)生什么對之前的決定都不改變。簡單的說就是一個局部最優(yōu)解的過程

介紹個例子就明白了：找零錢問題

假設(shè)有面值為5元、2元、1元、5角、2角、1角的貨幣，需要找給顧客4元6角現(xiàn)金，為使付出的貨幣的數(shù)量最少

　　首先找出小于4元6角的最大面值（2元）
　　其次找出小于2元6角的最大面值（2元）
　　接著找出小于6角的最大面值（5角）
　　最后找出小于1角的最大面值（1角） ---付出4張紙幣

介紹完了貪心算法簡單思想就利用該方法解決對應(yīng)問題

在已知股票價格走勢情況下只需要對下一天進行判斷如果漲了則買如果跌了則賣這樣收益會保持固定增長

當(dāng)然了有人會提出我可以選擇不賣等幾天再賣或不買等幾天再買的方式一樣可以保持增長但是如圖

如果在第2天買入 3天賣出 4天買入 5天賣出收益為A+B

如果在第2天買入 5天賣出收益為 C

明顯得出A+B大于C 所以貪心法在這種情況非常適用并且肯定得到最優(yōu)解

直接上代碼

class Solution(object):
  def maxProfit(self, prices):
    profit = 0
    for day in range(len(prices)-1):
      differ = prices[day+1] - prices[day]
      if differ > 0:
        profit += differ
    return profit
if __name__ == '__main__':
    test=Solution()
    prices = [5,7,3,9] # 輸入的每日股票數(shù)組
    print(test.maxProfit(prices))

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: