C ++中具有最大不同元素的子序列数
给我们一个仅包含整数的数组arr[]。目的是找到arr[]的子序列数，以使它们具有最大数量的不同元素。如果数组为[4,1,2,3,4]，则两个子序列将为[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，即数组本身。如果存在重复的元素，则每个重复的元素将成为新子序列的一部分。因此，我们将创建一个不同元素的频率的unordered_map。然后将每个频率乘以该频率进行计数。最后，计数具有频率总数。
以整数数组arr[]作为输入。
函数Max_distinct_subseq（intarr[]，intsize）获取数组及其大小，并返回具有最大不同元素的子序列的计数。
假设所有元素都是唯一的，则将初始计数设为1，则数组本身是具有最大不同元素的子序列。
创建unordered_map<int，int>哈希值；存储所有不同元素的频率。
使用for循环遍历数组，并使用hash[arr[i]]]++更新每个元素arr[i]的频率。
现在，使用for循环遍历哈希。对于每个频率，它->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