Chúng ta được cung cấp một mảng arr [] chỉ chứa các số nguyên. Mục đích là tìm số lượng các dãy con của arr [] sao cho chúng có số phần tử khác nhau tối đa. Nếu mảng là [4,1,2,3,4] thì hai dãy con sẽ là [4,1,2,3] và [1,2,3,4].
Hãy cho chúng tôi hiểu với các ví dụ
Đầu vào - arr [] ={1,3,5,4,2,3,1}
Đầu ra - Số lượng dãy con có tối đa các phần tử khác biệt là - 4
Giải thích - Các phần tử phân biệt tối đa là 1,2,3,4 và 5. Đếm là 5. Dãy con sẽ là -
[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 - Số lượng dãy con có tối đa các phần tử khác biệt là - 1
Giải thích - Tất cả các yếu tố là khác biệt. Số chuỗi con sẽ là 1.
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Trong cách tiếp cận này, chúng ta sẽ tìm các dãy con dựa trên thực tế là nếu tất cả các phần tử đều khác biệt thì số dãy con là 1 chính là mảng. Trong trường hợp có các phần tử lặp lại thì mỗi phần tử lặp lại sẽ là một phần của dãy con mới. Vì vậy, chúng tôi sẽ tạo một bản đồ tần số của các phần tử riêng biệt. Sau đó, với mỗi tần số nhân tần số đó để đếm. Ở cuối số đếm có tổng số tần số.
-
Lấy một mảng số nguyên arr [] làm đầu vào.
-
Hàm Max_distinct_subseq (int arr [], int size) nhận mảng và kích thước của nó và trả về số lượng các dãy con có tối đa các phần tử riêng biệt.
-
Lấy số lượng ban đầu là 1 vì nếu tất cả các phần tử đều khác biệt thì bản thân mảng là dãy con có tối đa các phần tử khác biệt.
-
Tạo bản đồ không có thứ tự
-
Duyệt qua mảng bằng cách sử dụng vòng lặp for và cập nhật tần số cho mỗi phần tử arr [i] bằng cách sử dụng hàm băm [arr [i]]] ++.
-
Bây giờ duyệt qua băm bằng vòng lặp for. Đối với mỗi tần số, nó-> giây (nó =biến lặp) nhân với số đếm trước đó. Vì x phần tử của cùng một thời điểm sẽ là một phần của x dãy con khác nhau.
-
Ở cuối số đếm có tổng số tần số.
-
Kết quả là số lượt trả lại.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count of subsequences having maximum distinct elements are: 3