C++で整数配列から3つの数の最大積を求めるアルゴリズム

問題の概要

整数型の配列が与えられます。この中から3つの数を選び、それらの積が最大になる組み合わせを見つけて、その最大積を返すことを考えましょう。

例えば、入力が [1, 1, 2, 3, 3] の場合、選択すべき3つの要素は [2, 3, 3] となるため、出力は 18 になります。

解決のアプローチ

この問題は、以下の手順で効率的に解くことができます。

• 配列 nums を昇順にソートする
• 配列のサイズを l とする
• 最大側の3要素 a = nums[l - 1]、b = nums[l - 2]、c = nums[l - 3] と、最小側の2要素 d = nums[0]、e = nums[1] を取り出す
• a × b × c と d × e × a のうち、大きい方を答えとして返す

なぜ最小の要素も比較する必要があるのか？

ポイントは「負の数同士を掛けると正の数になる」という性質です。配列に絶対値の大きい負の数が2つ含まれている場合、「その2つの負の数 × 最大の正の数」の積が、「最大の正の数3つの積」を上回る可能性があります。そのため、この2パターンを必ず比較しなければなりません。

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int maximumProduct(vector<int>& nums) {
      sort(nums.begin(), nums.end());
      int l = nums.size();
      int a = nums[l - 1], b = nums[l - 2], c = nums[l - 3], d = nums[0], e = nums[1];
      return max(a * b * c, d * e * a);
   }
};
main(){
   Solution ob;
   vector<int> v = {1,1,2,3,3};
   cout << (ob.maximumProduct(v));
}

入力

{1,1,2,3,3}

出力

18

計算量について

この解法の時間計算量は、ソート処理が支配的となるため O(n log n) です。空間計算量は追加の領域をほとんど使わないため O(1) となります。ソート済みの配列に対しては O(n) で処理できる点も魅力的です。