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

はじめに

数値のリストが与えられたとき、その中から異なる2つの要素を選び、その積（掛け算の結果）の最大値を求める問題を考えてみましょう。

例えば、入力が [5, 3, 7, 4] の場合を考えます。このとき最大の積は 7 × 5 = 35 となります。

解き方のアプローチ

最もシンプルな方法は、全ての要素ペアの組み合わせを調べる総当たり（ブルートフォース）による解法です。手順は以下の通りです。

• 現在の最大値を保持する変数 curr_max を負の無限大（-inf）で初期化します。
• 外側のループでインデックス i を 0 から要素数 - 1 まで回します。
• 内側のループでインデックス j を i + 1 から要素数 - 1 まで回し、同じペアを重複して調べないようにします。
• nums[i] * nums[j] が curr_max より大きければ、curr_max を更新します。
• すべてのペアを確認した後、curr_max を返します。

実装例

class Solution:
    def solve(self, nums):
        curr_max = float('-inf')
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if nums[i] * nums[j] > curr_max:
                    curr_max = nums[i] * nums[j]
        return curr_max

ob = Solution()
print(ob.solve([5, 3, 7, 4]))

入力

[5, 3, 7, 4]

出力

35

計算量について

この総当たりの解法では、2重ループを使用するため時間計算量は O(n²) となります。リストのサイズが小さい場合は十分実用的ですが、要素数が多い場合には効率が低下します。

より効率的な代替案：ソートを利用する方法

リストをあらかじめ昇順にソートしておけば、最大の積は以下のいずれかになります。

• 最も大きい2つの要素の積（末尾の2要素）
• 最も小さい2つの要素（負の数同士）の積

この性質を使うと、時間計算量 O(n log n) で解くことができます。

class Solution:
    def solve(self, nums):
        nums.sort()
        return max(nums[0] * nums[1], nums[-1] * nums[-2])

特に注意が必要なのは、リストに負の数が含まれるケースです。例えば [-10, -9, 1, 3] のような場合、最大の積は -10 × -9 = 90 となり、正の大きな数同士の組み合わせではなく、負の数同士の組み合わせが答えになります。上記のソートを使った方法なら、こうしたケースも自動的にカバーできます。

まとめ

本記事では、Pythonでリスト内の2つの異なる要素から最大の積を求める方法を紹介しました。理解しやすい総当たり法と、実務で有利なソート活用法の両方を押さえておくと、面接や実装の場面で役立ちます。