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]）

• 低：=inf、高：=−inf

• iからj− 1の範囲のkについては、do

  • dp（i、k）の残りごとに、実行

    • dp（k + 1、j）の各権利について、実行します

      • OPSのオペレーター操作ごとに、以下を実行します

        • res：=左操作右

        • res

          • 低：=解像度

        • res> highの場合、

          • 高：=解像度

• リターンペア（低、高）

• メインの方法から、次のようにします-

• ans：=dp（0、N − 1）

• ansの2番目の値を返す

理解を深めるために、次の実装を見てみましょう-

例

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