Đếm số dãy con có số phần tử phân biệt tối đa trong C++

Cho mảng arr[]. Tìm số dãy con (subsequence) có số phần tử phân biệt tối đa. Ví dụ: [4,1,2,3,4] → 2 dãy con: [4,1,2,3] và [1,2,3,4].

Ví dụ

Đầu vào − arr[] = {1,3,5,4,2,3,1}

Đầu ra − 4

Giải thích − Các phần tử phân biệt tối đa: 1,2,3,4,5 (5 phần tử). 4 dãy con: [1,3,5,4,2], [3,5,4,2,1], [5,4,2,3,1], [1,5,4,2,3].

Đầu vào − arr[] = {5,4,2,1,3}

Đầu ra − 1

Giải thích − Tất cả phân biệt → chỉ 1 dãy con (chính mảng đó).

Phương pháp giải

Nếu tất cả phân biệt → 1 dãy con. Nếu có phần tử lặp, mỗi lần lặp tạo ra dãy con mới. Dùng unordered_map đếm tần suất. Kết quả = tích các tần suất.

• Hàm Max_distinct_subseq(int arr[], int size).
• count = 1.
• unordered_map hash đếm tần suất.
• Duyệt hash: count *= it->second.
• Trả về count.

Ví dụ code

#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 *= 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;
}

Đầu ra

Count of subsequences having maximum distinct elements are: 3