C++でサイズkの部分列における最大積を求めるアルゴリズム

この問題では、整数の配列 arr[] と数値 k が与えられ、サイズ k の部分列のうち要素の積が最大になるものを求めるプログラムを C++ で作成します。

問題の概要

サイズ k(1 ≤ k ≤ n)の部分列の中から、その要素の積が最大となるものを見つけることが目的です。

入力例

arr[] = {1, 5, 6, -2, 0, 4} , k = 3

出力例

120

説明

サイズ 3 の部分列の中で最大の積となるのは (5, 6, 4) であり、その積は 120 です。

解決アプローチ

この問題を解くには、まず配列 arr[] をソートし、その後、配列の要素の値と k の値に応じて処理方法を切り替えます。以下のようなケースに分けて考えます。

ケース1(kが偶数の場合)

0 を除く最大の k 個の値を採用することで最大積が得られます。ただし、負の値のペアも考慮する必要があります。負の値同士を掛け合わせると正になるため、その絶対値の大きさによっては結果が最大になる可能性があるからです。

ケース2(kが奇数の場合)

このケースはやや複雑で、配列の最大要素の値によって計算方法が変わります。さらに以下の3つに分類できます。

ケース2.1(最大値が正の場合) ― 配列に正と負の数が混在していることを意味します。この場合、最大の k 個の要素を選びつつ、負の側から最大のペアを探索し(可能であれば)、どちらがより大きな積を生むかを比較します。

ケース2.2(最大値が0の場合) ― 配列がすべて負の数と 0 で構成されていることを意味します。奇数個の負の数を掛け合わせると結果は必ず負になるため、最大の積は 0 となります。

ケース2.3(最大値が負の場合) ― 配列がすべて負の数で構成されていることを意味します。この場合、絶対値が最小の要素(つまりソート後の配列で最大の要素)を掛け合わせたものが最大の積となります。

このように、最適な結果を得るためには、配列の要素の値と k の値の両方を常にチェックする必要があります。そのため、配列の最大側と最小側の両端を保持しながら、負のペアを掛け合わせることでより良い結果が得られるかどうかを判定していきます。

実装例

以下は、この解法の動作を示すC++プログラムです。

#include <bits/stdc++.h>
using namespace std;
int findMaxSubArrayProduct(int arr[], int n, int k) {
   sort(arr, arr + n);
   int maxProd = 1;
   int i = 0, j = 0;
   int maxprod, minprod;
   if (arr[n - 1] == 0 && (k % 2 == 1))
      return 0;
   if (arr[n - 1] <= 0 && (k % 2 == 1)) {
      for (i = n - 1; i >= n - k; i--)
         maxProd *= arr[i];
         return maxProd;
   }
   i = 0;
   j = n - 1;
   if (k % 2 == 1) {
      maxProd *= arr[j];
      j--;
      k--;
   }
   k = k/2;
   int it = 0;
   while(it < k){
      int minprod = arr[i] * arr[i + 1];
      int maxprod = arr[j] * arr[j - 1];
      if (minprod > maxprod) {
         maxProd *= minprod;
         i += 2;
      } else {
         maxProd *= maxprod;
         j -= 2;
      }
      it++;
   }
   return maxProd;
}
int main() {
   int arr[] = { 1, 5, 6, -2, 0, 4 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int k = 3;
   cout<<"The maximum product of subsequence of size "<<k<<" is "<<findMaxSubArrayProduct(arr, n, k);
   return 0;
}

出力

The maximum product of subsequence of size 3 is 120

このアルゴリズムの計算量は、ソートに O(n log n)、その後の選択処理に O(k) かかるため、全体として O(n log n) となります。負の数を含む配列でも正しく最大積を求められる点がポイントです。