Python程式：求解買賣股票最大利潤

假設我們按時間順序獲得了一個公司股票價格的列表，我們需要找到透過買賣股票可以獲得的最大利潤。必須先買入後賣出，並且賣出股票後必須等待一天才能再次買入。

因此，如果輸入類似 prices = [2, 6, 9, 4, 11]，則輸出為 11，因為我們可以以 2 買入，以 6 賣出，等待一天，然後以 4 買入，然後以 11 賣出。

為了解決這個問題，我們將遵循以下步驟：

• s := 0

• b := -∞

• 對於 i 從 0 到 prices 的大小，執行：

  • temp := b

  • b := max(b, (s - prices[i]))

  • 如果 i 非零，則：

    • s := max(s, (temp + prices[i - 1]))

• 返回 max(s, (b + prices 的最後一個元素))

讓我們看看下面的實現以更好地理解。

示例

線上演示

class Solution:
   def solve(self, prices):
      s = 0
      b = float("-inf")
      for i in range(len(prices)):
         temp = b
         b = max(b, s - prices[i])
         if i:
            s = max(s, temp + prices[i - 1])
      return max(s, b + prices[-1])

ob = Solution()
prices = [2, 6, 9, 4, 11]
print(ob.solve(prices))

輸入

[2, 6, 9, 4, 11]

輸出

11

Arnab Chakraborty

更新於：2020年11月10日

瀏覽量：152

開啟您的職業生涯

完成課程獲得認證

開始學習