Python 中股票最佳買賣時機

假設我們有一個數組 A，其中 A[i] 表示某一天的股票價格。我們需要找到最大利潤。我們最多可以完成一筆交易。（交易意味著買賣股票）。但我們必須記住，我們不能同時進行多筆交易。因此，我們必須在購買新股票之前賣出股票。

假設陣列如下：A = [7, 1, 5, 3, 6, 4]，則結果為 5。我們可以看到，如果我們在第 2 天（索引 1）購買，則購買價格為 1。然後，如果我們在第 5 天賣出，利潤將為 6 – 1 = 5。

要解決此問題，請按照以下步驟操作：

  • 建立兩個與 A 大小相同的陣列 leftMin 和 rightMax，並用 0 填充它們
  • leftMin[0] = A[0]
  • 對於 i 從 1 到 A 的長度 – 1，leftMin[i] = leftMin[i – 1] 和 A[i] 的最小值
  • rightMax[n-1] = A[n – 1]
  • 對於 i 從 A 的長度 – 1 到 1，rightMax[i] = rightMax[i + 1] 和 A[i] 的最大值
  • 設定答案 := 0
  • 對於 i 從 0 到 A 的長度 – 1，答案 := 答案和 rightMax[i + 1] – leftMin[i] 的最大值
  • 返回答案

讓我們看看實現來更好地理解

示例

 現場演示

class Solution(object):
   def maxProfit(self, prices):
      """
      :type prices: List[int]
      :rtype: int
      """
      if not prices:
         return 0
      leftMin,rightMax = [0 for i in range(len(prices))],[0 for i in range(len(prices))]
      leftMin[0] = prices[0]
      for i in range(1,len(prices)):
         leftMin[i] = min(leftMin[i-1],prices[i])
      #print(leftMin)
      rightMax[-1]= prices[-1]
      for i in range(len(prices)-2,-1,-1):
         rightMax[i] = max(rightMax[i+1],prices[i])
      #print(rightMax)
      ans = 0
      for i in range(len(prices)-1):
         ans = max(ans,rightMax[i+1]-leftMin[i])
      return ans
ob1 = Solution()
print(ob1.maxProfit([7,2,5,8,6,3,1,4,5,4,7]))

輸入

prices = [7,2,5,8,6,3,1,4,5,4,7]

輸出

6

更新於： 2020-04-28

417 次檢視

開啟您的 職業生涯

透過完成課程獲得認證

開始
廣告