C++で配列から最大積・最小積の部分集合を求めるアルゴリズム

サイズ N の整数型配列が与えられます。この記事の目的は、その配列の中から「最大積」と「最小積」を生み出す部分集合を見つけることです。ここでは、これまでに見つかった最大積を保持する maxProd、最小積を保持する minProd という2つの変数を使って問題を解いていきます。

配列を先頭から走査しながら、各要素を maxProd と minProd の両方に掛けていきます。同時に、直前の最大積(prevMax)、直前の最小積(prevMin)、現在の最大積(curMax)、現在の最小積(curMin)、そして現在の要素そのものも常にチェックすることがポイントです。

入力例

Arr[]= { 1,2,5,0,2 }

出力

Maximum Product: 20
Minimum Product: 0

説明 − 配列の2番目の要素から処理を開始し、maxProd と minProd は最初の要素(1)で初期化します。各ステップの動きは以下の通りです。

Arr[1]: 1*2=2, 1*2=2, maxProd=2, minProd=1
Arr[2]: 2*5=10, 1*5=5, maxProd=10, minProd=1
Arr[3]: 10*0=0, 1*0=0, maxProd=10, minProd=0
Arr[4]: 10*2=20, 0*2=0, maxProd=20, minProd=0

入力例(負の数を含む場合)

Arr[]= { -1,2,-5,0,2 }

出力

Maximum Product: 20
Minimum Product: -20

説明 − 最大積となる部分集合は { -1,2,-5,2 } の要素で構成されます。負の数が2つ含まれるため、それらを掛け合わせることで正の大きな積が得られます。

一方、最小積となる部分集合は { 2,-5,2 } の要素で構成され、負の数が1つだけ残るためマイナスの積になります。

プログラムで使用しているアプローチ

• 整数型配列 Arr[] には正と負の整数が含まれています。

• 変数 size には配列の長さが格納されます。

• 関数 getProductSubset(int arr[], int n) は配列を引数として受け取り、そこから得られる最大積と最小積を出力します。

• 変数 curMin、curMax は、現時点で見つかっている最大積・最小積を格納します。初期値は arr[0] です。

• 変数 prevMin、prevMax は、直前の最大積・最小積を格納します。初期値は arr[0] です。

• 変数 maxProd、minProd は、最終的に得られた最大積・最小積を格納します。

• 配列の走査は2番目の要素 arr[1] から最後のインデックスまで行います。

• 最大積を求めるには、現在の arr[i] を prevMax および prevMin の両方と掛け合わせます。その結果の最大値を curMax に保存し、さらに prevMax とも比較して大きい方を curMax とします。

• curMax が maxProd より大きい場合は、maxProd を curMax で更新します。

• 最後に、次の反復処理に備えて prevMax を curMax で更新します。

• prevMin、curMin、minProd についても、比較条件を逆にして同じ手順を実行します。

• ループ終了後、maxProd と minProd に格納された結果を出力します。

実装例(C++)

#include <iostream>
using namespace std;
void getProductSubset(int arr[], int n){
    // すべての積を arr[0] で初期化
    int curMax = arr[0];
    int curMin = arr[0];
    int prevMax = arr[0];
    int prevMin = arr[0];
    int maxProd = arr[0];
    int minProd = arr[0];
    int temp1=0,temp2=0,temp3=0;
    // arr[0] 以降のすべての要素を処理
    for (int i = 1; i < n; ++i){
        /* 現在の最大積は以下のうちの最大値
        1) prevMax * 現在の arr[i](arr[i] が正の場合)
        2) prevMin * 現在の arr[i](arr[i] が負の場合)
        3) 現在の arr[i]
        4) 直前の最大積 */
        temp1=prevMax*arr[i];
        temp2=prevMin*arr[i];
        temp3=temp1>temp2?temp1:temp2;
        curMax = temp3>arr[i]?temp3:arr[i];
        curMax = curMax>prevMax?curMax:prevMax;
        /* 現在の最小積は以下のうちの最小値
        1) prevMin * 現在の arr[i](arr[i] が正の場合)
        2) prevMax * 現在の arr[i](arr[i] が負の場合)
        3) 現在の arr[i]
        4) 直前の最小積 */
        temp1=prevMax*arr[i];
        temp2=prevMin*arr[i];
        temp3=temp1<temp2?temp1:temp2;
        curMin = temp3<arr[i]?temp3:arr[i];
        curMin = curMin<prevMin?curMin:prevMin;
        maxProd = maxProd>curMax?maxProd:curMax;
        minProd = minProd<curMin?minProd:curMin;
        // 現在の値を前回の値としてコピー
        prevMax = curMax;
        prevMin = curMin;
    }
    std::cout<<"Maximum Subset Product: "<<maxProd;
    std::cout<<"\nMinimum Subset Product: "<<minProd;
}
int main(){
    int Arr[] = {-4, -3, 1, 2, 0, 8, 1};
    // int arr[] = {-4, 1,1, 3, 5,7};
    int size = 7;
    getProductSubset(Arr,size );
    return 0;
}

出力

Maximum Subset Product: 192
Minimum Subset Product: -64

計算量について

このアルゴリズムは配列を一度だけ走査すればよいため、時間計算量は O(N) です。また、使用する変数は固定個数のみなので、追加の記憶領域も O(1) で済みます。負の数やゼロを含む配列でも正しく動作する点が、単純な全要素の積を求める方法との大きな違いです。