C++で最大の個別要素を持つサブシーケンスの数

整数のみを含む配列arr[]が与えられます。目標は、arr []のサブシーケンスの数を見つけて、それらが最大数の個別の要素を持つようにすることです。配列が[4,1,2,3,4]の場合、2つのサブシーケンスは[4,1,2,3]と[1,2,3,4]になります。

例を挙げて理解しましょう

入力 − arr [] ={1,3,5,4,2,3,1}

出力 −最大の個別要素を持つサブシーケンスの数は− 4

説明 −最大の個別要素は1、2、3、4、および5です。カウントは5です。サブシーケンスは-

[1,3,5,4,2]、[3,5,4,2,1]、[5,4,2,3,1]、[1,5,4,2,3]。

入力 − arr [] ={5,4,2,1,3}

出力 −最大の個別要素を持つサブシーケンスの数は− 1

説明 −すべての要素が異なります。サブシーケンスの数は1になります。

以下のプログラムで使用されているアプローチは次のとおりです

このアプローチでは、すべての要素が異なる場合、サブシーケンスの数は配列自体である1であるという事実に基づいて、サブシーケンスを見つけます。繰り返される要素がある場合、繰り返される各要素は新しいサブシーケンスの一部になります。したがって、個別の要素の頻度のunorderdered_mapを作成します。次に、周波数ごとにその周波数を掛けてカウントします。最後に、カウントには頻度の総数があります。

• 整数配列arr[]を入力として受け取ります。

• 関数Max_distinct_subseq（int arr []、int size）は、配列とそのサイズを取得し、最大の個別要素を持つサブシーケンスの数を返します。

• すべての要素が別個であるかのように、初期カウントを1とすると、配列自体は最大の別個の要素を持つサブシーケンスになります。

• unordered_map ハッシュを作成します。すべての異なる要素の頻度を保存します。

• forループを使用して配列をトラバースし、hash [arr[i]]]++を使用して各要素arr[i]の頻度を更新します。

• 次に、forループを使用してハッシュをトラバースします。各周波数について、it-> second（it =iterator）は前のカウントに乗算します。同時にx個の要素がx個の異なるサブシーケンスの一部になるため。

• 最後に、カウントには頻度の総数があります。

• 結果としてカウントを返します。

例

#include <bits/stdc++.h>
using namespace std;
int Max_distinct_subseq(int arr[], int size){
   int count = 1;
   unordered_map<int, int> hash;
   for (int i = 0; i < size; i++){
      hash[arr[i]]++;
   }
   for (auto it = hash.begin(); it != hash.end(); it++){
      count = count * (it->second);
   }
   return count;
}
int main(){
   int arr[] = { 3, 7, 3, 3, 1, 5, 6, 9 };
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Count of subsequences having maximum distinct elements are: "<<Max_distinct_subseq(arr, size);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count of subsequences having maximum distinct elements are: 3