Python程式：在數字之間插入運算子以查詢最大值

假設我們有一組數字，稱為nums，我們需要找到透過在給定數字之間新增任何二元運算子（例如+，-和*）以及插入任何有效括號可以生成的 最大值。

因此，如果輸入類似於nums = [-6，-4，-10]，則輸出將為100，因為我們可以建立類似於：((-6) + (-4)) * -10 的表示式。

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

  • OPS := 運算子列表 [+, -, *]

  • N := A 的大小

  • 如果A中的所有元素都是0，則

    • 返回 0

  • 定義一個函式 dp()。這將採用 i, j

  • 如果 i 等於 j，則

    • 返回一個 (A[i], A[i]) 對

  • low := inf, high := -inf

  • 對於 k 的範圍從 i 到 j - 1，執行以下操作：

    • 對於 dp(i, k) 中的每個 left，執行以下操作：

      • 對於 dp(k + 1, j) 中的每個 right，執行以下操作：

        • 對於 OPS 中的每個運算子 op，執行以下操作：

          • res := left op right

          • 如果 res < low，則

            • low := res

          • 如果 res > high，則

            • high := res

  • 返回 (low, high) 對

  • 從主方法執行以下操作：

  • ans := dp(0, N - 1)

  • 返回 ans 的第二個值

讓我們看一下下面的實現，以便更好地理解：

示例

線上演示

import operator
class Solution:
   def solve(self, A):
      OPS = [operator.add, operator.sub, operator.mul]
      N = len(A)
      if not any(A):
         return 0
      def dp(i, j):
         if i == j:
            return [A[i], A[i]]
         low = float("inf")
         high = float("−inf")
         for k in range(i, j):
            for left in dp(i, k):
               for right in dp(k + 1, j):
                  for op in OPS:
                     res = op(left, right)
                     if res < low:
                        low = res
                     if res > high:
                        high = res
         return [low, high]
      return dp(0, N − 1)[1]
ob = Solution()
nums = [−6, −4, −10]
print(ob.solve(nums))

輸入

[−6, −4, −10]

輸出

100

更新於：2020年12月15日

264 次瀏覽

啟動您的職業生涯

完成課程獲得認證

開始學習
廣告