अधिकतम विशिष्ट तत्वों वाले उपअनुक्रमों की गणना - C++

समस्या विवरण

हमें एक पूर्णांक सरणी दी गई है। लक्ष्य उन उपअनुक्रमों की संख्या ज्ञात करना है जिनमें अधिकतम संभव विशिष्ट तत्व हों।

उदाहरण

इनपुट: 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. प्रारंभिक count = 1
2. अनऑर्डर्ड मैप hash में आवृत्तियाँ गिनें
3. प्रत्येक आवृत्ति freq के लिए: count *= freq
4. count लौटाएँ

C++ कार्यान्वयन

#include <bits/stdc++.h>
using namespace std;

int Max_distinct_subseq(int arr[], int size) {
    int count = 1;
    unordered_map hash;
    
    for (int i = 0; i < size; i++) hash[arr[i]]++;
    
    for (auto& it : hash) 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: " << Max_distinct_subseq(arr, size);
    return 0;
}

आउटपुट

Count: 3