Pythonで数値の間に演算子と括弧を挿入して最大値を求めるプログラム

問題概要

nums という数値のリストが与えられているとします。この数値同士の間に +、−、* などの二項演算子を挿入し、さらに有効な括弧を任意に追加することで構成できる式の中から、生成できる値の最大値を求めるのが課題です。

たとえば、入力が nums = [-6, -4, -10] の場合、((-6) + (-4)) × (-10) という式を作ることができるため、出力は 100 となります。

解き方（アルゴリズム）

この問題は区間DP（インターバル・ダイナミックプログラミング）を用いて効率的に解けます。重要なポイントは、各区間について「最小値」と「最大値」の両方を記録することです。負の数同士を掛け合わせると大きな正の数になる可能性があるため、最小値も追跡しておく必要があります。

具体的な手順は以下の通りです。

1. OPS := 演算子のリスト [+, −, *] を用意する
2. N := リスト A の要素数とする
3. A のすべての要素が 0 の場合は 0 を返す
4. 関数 dp(i, j) を定義する（区間 i〜j の結果を返す）
5. i == j の場合、ペア (A[i], A[i]) を返す
6. low := 無限大、high := 負の無限大で初期化する
7. k を i から j − 1 の範囲でループし、dp(i, k) の各左辺の値 left と dp(k + 1, j) の各右辺の値 right のすべての組み合わせに対して、OPS 内の各演算子 op を適用して res = left op right を計算する
8. res が low より小さければ low を更新し、high より大きければ high を更新する
9. 最後にペア (low, high) を返す

メイン処理では ans := dp(0, N − 1) を呼び出し、ans の2番目の要素（最大値）を結果として返します。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

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

計算量と補足

このアルゴリズムの時間計算量は O(N³ × |OPS|)、空間計算量は O(N²) です。再帰呼び出しが重複する場合は、functools.lru_cache デコレーターを使ってメモ化すると、大幅に高速化できます。負の数が含まれるリストでは掛け算によって符号が反転するため、最小値と最大値の両方を保持する設計が正しい答えを保証する鍵となります。