C++で整数配列から最大の積を持つペアを見つける方法

配列Aにn個の異なる要素が含まれているとします。この配列Aから、積が最大になるペア(x, y)を見つける必要があります。配列には正の要素だけでなく、負の要素も含まれている可能性がある点に注意しましょう。

例えば、配列が A = [-1, -4, -3, 0, 2, -5] の場合、(-4, -5) のペアが最大の積(20)を持つため、これが答えとなります。負の数同士を掛け合わせると正の数になるため、このようなケースが生じます。

解決のアプローチ

この問題を解くには、配列を一度走査しながら以下の4つの値を追跡します。

• positive_max:正の要素の最大値
• positive_second_max:正の要素で2番目に大きい値
• neg_max:絶対値が最大の負の要素
• neg_second_max:絶対値が2番目に大きい負の要素

走査が完了した後、(positive_max × positive_second_max) が (neg_max × neg_second_max) より大きければ正のペアを返し、そうでなければ負のペアを返します。この方法なら、時間計算量O(n)・空間計算量O(1)で効率的に解くことができます。

サンプルコード

#include<iostream>
#include<cmath>
using namespace std;
void maxProdPair(int arr[], int n) {
   if (n < 2) {
      cout << "No pair is present";
      return;
   }
   if (n == 2) {
      cout << "(" << arr[0] << ", " << arr[1] << ")" << endl;
      return;
   }
   int pos_max = INT_MIN, pos_second_max = INT_MIN;
   int neg_max = INT_MIN, neg_second_max = INT_MIN;
   for (int i = 0; i < n; i++) {
      if (arr[i] > pos_max) {
         pos_second_max = pos_max;
         pos_max = arr[i];
      } else if (arr[i] > pos_second_max)
      pos_second_max = arr[i];
      if (arr[i] < 0 && abs(arr[i]) > abs(neg_max)) {
         neg_second_max = neg_max;
         neg_max = arr[i];
      }
      else if(arr[i] < 0 && abs(arr[i]) > abs(neg_second_max))
      neg_second_max = arr[i];
   }
   if (neg_max*neg_second_max > pos_max*pos_second_max)
      cout << "(" << neg_max << ", " << neg_second_max << ")" << endl;
   else
      cout << "(" << pos_max << ", " << pos_second_max << ")" << endl;
}
int main() {
   int arr[] = {-1, -4, -3, 0, 2, -5};
   int n = sizeof(arr)/sizeof(arr[0]);
   maxProdPair(arr, n);
}

実行結果

(-5, -4)

このコードでは、まず要素数が2未満の場合はペアが存在しないためメッセージを表示して終了します。要素数がちょうど2の場合は、その2つの要素がそのまま答えとなります。それ以外の場合は、ループ内で正の値と負の値(絶対値)それぞれの最大値と2番目の値を更新していき、最終的に両者の積を比較して大きい方のペアを出力します。

このサンプルでは、負の数同士の積 (-5) × (-4) = 20 が正の数同士の積 0 × 2 = 0 よりも大きいため、(-5, -4) が出力されます。