Pythonでリスト内の3つの要素から最大の積を求めるプログラム

数値のリスト nums が与えられたとき、その中から3つの異なる要素を選んで掛け合わせたときの最大値を求める問題を考えてみましょう。

例えば、入力が nums = [6, 1, 2, 4, -3, -4] の場合、出力は 72 になります。これは、(-3) × (-4) × 6 = 72 となるためです。負の数同士を掛けると正の数になるため、小さな負の数2つと大きな正の数1つを組み合わせるのがポイントになります。

解法のアプローチ

この問題は、リストをソートすることで効率的に解くことができます。最大の積が得られる候補は次の2パターンだけだからです。

• 最小の2つの負の数 × 最大の正の数: 負の数2つを掛けると正になり、絶対値が大きいほど結果も大きくなります。
• 最大の3つの数の積: すべて正の数、または一般的なケースで最も単純な候補です。

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

1. リスト nums を昇順にソートする
2. n をリストのサイズとする
3. maxScore を非常に小さい値(−無限大)で初期化する
4. maxScore と nums[0] * nums[1] * nums[n-1](最小2つ×最大1つ)の大きい方を maxScore に代入する
5. maxScore と nums[n-3] * nums[n-2] * nums[n-1](最大3つの積)の大きい方を maxScore に代入する
6. maxScore を返す

実装例

それでは、実際のコードを見てみましょう。

def solve(nums):
    nums.sort()
    n = len(nums)
    maxScore = float('-inf')
    maxScore = max(maxScore, nums[0] * nums[1] * nums[n - 1])
    maxScore = max(maxScore, nums[n - 3] * nums[n - 2] * nums[n - 1])
    return maxScore

nums = [6, 1, 2, 4, -3, -4]
print(solve(nums))

入力

[6, 1, 2, 4, -3, -4]

出力

72

計算量について

この解法の時間計算量は、ソートに依存して O(n log n) となります。空間計算量は追加のデータ構造を使わないため O(1) です。全ての3要素の組み合わせを試す総当たり法(O(n³))と比べて、大幅に効率的であることがわかります。