Pythonで2つのリストの要素を掛け合わせた合計の最大値を求めるプログラム

本記事では、2つのリスト nums と multipliers を使って、掛け合わせた数値の合計が最大になる組み合わせを求めるアルゴリズムを解説します。

問題の概要

次のような操作を考えます。nums から任意の数を1つ取り除き、multipliers からも任意の数を1つ取り除いて、その2つの数を掛け合わせます。この操作をどちらか一方のリストが空になるまで繰り返し、最終的な掛け算の結果の合計の最大値を求めるのが目的です。

例として、入力が nums = [-4, 4, 3]、multipliers = [-2, 2] の場合を考えてみましょう。このとき出力は 16 になります。これは、-4 と -2、そして 4 と 2 をそれぞれ組み合わせて -4 × -2 + 4 × 2 = 8 + 8 = 16 となるためです。

解法のアプローチ

この問題は貪欲法（グリーディ法）で効率的に解くことができます。ポイントは以下の通りです。

• 負の乗数には、リスト内の最小値（負の数）を掛け合わせる。負同士の掛け算は正になるため、絶対値の大きい負の数同士を組み合わせるほど合計が大きくなります。
• 正の乗数には、リスト内の最大値（正の数）を掛け合わせることで合計を最大化できます。

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

1. リスト nums を昇順にソートする
2. リスト multipliers を昇順にソートする
3. 結果を格納する変数 res を 0 で初期化する
4. nums のサイズが multipliers より小さい場合は、両者を入れ替える
5. n を nums のサイズ、m を multipliers のサイズとする
6. i を 0 から m - 1 まで繰り返す：
   • multipliers[i] <= 0 の場合は、res += nums[i] * multipliers[i]（最小側の要素と組み合わせ）
   • それ以外の場合は、res += multipliers[i] * nums[n - (m - i)]（最大側の要素と組み合わせ）
7. res を返す

Pythonでの実装例

以下に実際の実装コードを示します。

def solve(nums, multipliers):
    nums.sort()
    multipliers.sort()
    res = 0
    if len(nums) < len(multipliers):
        nums, multipliers = multipliers, nums

    n, m = len(nums), len(multipliers)
    for i in range(m):
        if multipliers[i] <= 0:
            res += nums[i] * multipliers[i]
        else:
            res += multipliers[i] * nums[n - (m - i)]
    return res

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

入力

[-4, 4, 3], [-2, 2]

出力

16

処理の流れを詳しく見る

上記の入力例では、まず両リストがソートされ、nums = [-4, 3, 4]、multipliers = [-2, 2] となります。

• i = 0 のとき：multipliers[0] = -2 は負なので、nums[0] = -4 と組み合わせ → -4 × -2 = 8
• i = 1 のとき：multipliers[1] = 2 は正なので、nums[n - (m - i)] = nums[3 - 1] = nums[2] = 4 と組み合わせ → 2 × 4 = 8

合計は 8 + 8 = 16 となり、期待通りの結果が得られます。

計算量について

このアルゴリズムの計算量は、ソートが支配的となるため O(n log n) です。全ての組み合わせを試す総当たり方式では指数時間かかりますが、この方法なら大規模な入力でも高速に動作します。