정수만 포함하는 배열 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(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