นับซับลำดับที่มีสมาชิกต่างกันสูงสุดใน 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 ของความถี่ของสมาชิกที่ต่างกัน แล้วสำหรับแต่ละความถี่ คูณความถี่นั้นเข้ากับ count ท้ายสุด count จะมีจำนวนความถี่รวม

• รับอาเรย์จำนวนเต็ม arr[] เป็นอินพุต
• ฟังก์ชัน Max_distinct_subseq(int arr[], int size) รับอาเรย์และขนาด คืนจำนวนซับลำดับที่มีสมาชิกต่างกันสูงสุด
• กำหนด count เริ่มต้นเป็น 1 เนื่องจากถ้าสมาชิกทั้งหมดต่างกัน อาเรย์เองคือซับลำดับที่มีสมาชิกต่างกันสูงสุด
• สร้าง unordered_map<int, int> hash เก็บความถี่ของสมาชิกที่ต่างกันทั้งหมด
• เดินทางอาเรย์ด้วยลูป FOR อัปเดตความถี่สำหรับแต่ละสมาชิก arr[i] ด้วย hash[arr[i]]++
• เดินทาง hash ด้วยลูป FOR สำหรับแต่ละความถี่ it->second (it=iterator) คูณเข้ากับ count ก่อนหน้า เนื่องจาก x สมาชิกที่เหมือนกันจะเป็นส่วนหนึ่งของ x ซับลำดับที่ต่างกัน
• ท้ายสุด count มีจำนวนความถี่รวม
• คืน count

ตัวอย่างโค้ด C++

#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