通过在Python中的数字之间插入运算符来查找最大值的程序

Z时代
2024-01-10
分类：综合

假设我们有一个称为nums的数字列表，我们必须找到可以通过在给定数字之间添加+，-和*之类的任何二进制运算符并插入任何有效的括号来生成的最大值。

因此，如果输入类似于nums = [−6，-4，-10]，则输出将为100，因为我们可以使表达式像：（（−6）+（−4））* -10。

为了解决这个问题，我们将遵循以下步骤-

OPS：=运算符列表[+，−，*]
N：= A的大小
如果A中的所有元素均为0，则

返回0

定义一个功能dp()。这需要我，j
如果我和j相同

返回一对（A [i]，A [i]）

低：= inf，高：= -inf
对于在i到j − 1范围内的k

对于dp（k + 1，j）中的每个右，
res：=左op右
如果res <低，则
如果res> high，则
低：= res
高：= res

对于OPS中的每个运算符op，
对于剩下的每个dp(i, k)，

返回对（低，高）
从主要方法中执行以下操作-
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))