Given an array arr[], the task is to rearrange the array to generate maximum decreasing subsequences and print the count of the maximum number of subsequences possible such that each array element can be part of a single subsequence and the length of the subsequences needs to be maximized.
Example:
Input: arr[] = {5, 2, 3, 4}
Output: 1
Explanation:
The given array can be rearranged to {5, 4, 3, 2}.
Since every element is occurring only once, the rearranged array forms a decreasing subsequence of maximum possible length.Input: arr[] = {5, 2, 6, 5, 2, 4, 5, 2}
Output: 3
Explanation:
The given array can be rearranged to {5, 2, 6, 5, 4, 2, 5, 2}.
The 3 decreasing subsequences of maximum possible length possible from the given array are {6, 5, 4, 2}, {5, 2} and {5, 2}
Approach:
To solve the problem, there is no need to actually rearrange the given array. Since every element can be part of a single subsequence, the number of subsequences will be equal to the frequency of the most frequent element.
Follow the steps below to solve the problem:
- Traverse the array and store the frequency of each array element in a Hashmap
- Now, traverse the HashMap to find the maximum frequency of an element in an array.
- Print the maximum frequency as the count of maximum decreasing subsequences possible.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to count maximum subsequencevoid Maximum_subsequence(int A[], int N){ // Stores the frequency // of array elements unordered_map<int, int> frequency; // Stores max frequency int max_freq = 0; for (int i = 0; i < N; i++) { // Update frequency of A[i] frequency[A[i]]++; } for (auto it : frequency) { // Update max subsequence if (it.second > max_freq) { max_freq = it.second; } } // Print the count cout << max_freq << endl;}// Driver Codeint main(){ int arr[] = { 5, 2, 6, 5, 2, 4, 5, 2 }; int N = sizeof(arr) / sizeof(arr[0]); Maximum_subsequence(arr, N); return 0;} |
Java
// Java program for rearrange array// to generate maximum decreasing// subsequencesimport java.util.HashMap;import java.util.Map;public class Main { // Function to count maximum subsequence public static void Maximum_subsequence( int[] A, int N) { // Stores the frequency // of array elements HashMap<Integer, Integer> frequency = new HashMap<>(); // Stores maximum frequency int max_freq = 0; for (int i = 0; i < N; i++) { // Update frequency of A[i] if (frequency.containsKey(A[i])) { frequency.replace(A[i], frequency.get(A[i]) + 1); } else { frequency.put(A[i], 1); } } for (Map.Entry it : frequency.entrySet()) { // Update maximum subsequences if ((int)it.getValue() > max_freq) { max_freq = (int)it.getValue(); } } // Print the result System.out.println(max_freq); } // Driver Code public static void main(String[] args) { int arr[] = { 5, 2, 6, 5, 2, 4, 5, 2 }; int N = arr.length; Maximum_subsequence(arr, N); }} |
Python3
# Python3 program to implement # the above approach # Function to count maximum subsequence def Maximum_subsequence(A, N): # Stores the frequency # of array elements frequency = dict(); # Stores max frequency max_freq = 0; for i in range(N): if (A[i] in frequency): frequency[A[i]] += 1 else: frequency[A[i]] = 1 for it in frequency: # Update max subsequence if (frequency[it] > max_freq): max_freq = frequency[it]; # Print the count print(max_freq); # Driver Code arr = [ 5, 2, 6, 5, 2, 4, 5, 2 ]; Maximum_subsequence(arr, len(arr)); # This code is contributed by grand_master |
C#
// C# program for rearrange array// to generate maximum decreasing// subsequencesusing System;using System.Collections.Generic;class GFG{ // Function to count maximum subsequencepublic static void Maximum_subsequence(int[] A, int N){ // Stores the frequency // of array elements Dictionary<int, int> frequency = new Dictionary<int, int>(); // Stores maximum frequency int max_freq = 0; for(int i = 0; i < N; i++) { // Update frequency of A[i] if (frequency.ContainsKey(A[i])) { frequency[A[i]] = frequency[A[i]] + 1; } else { frequency.Add(A[i], 1); } } foreach(KeyValuePair<int, int> it in frequency) { // Update maximum subsequences if ((int)it.Value > max_freq) { max_freq = (int)it.Value; } } // Print the result Console.WriteLine(max_freq);}// Driver Codepublic static void Main(String[] args){ int []arr = { 5, 2, 6, 5, 2, 4, 5, 2 }; int N = arr.Length; Maximum_subsequence(arr, N);}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript Program to implement// the above approach// Function to count maximum subsequencefunction Maximum_subsequence(A, N){ // Stores the frequency // of array elements var frequency = new Map(); // Stores max frequency var max_freq = 0; for (var i = 0; i < N; i++) { // Update frequency of A[i] if(frequency.has(A[i])) frequency.set(A[i], frequency.get(A[i])+1) else frequency.set(A[i], 1); } frequency.forEach((value, key) => { // Update max subsequence if (value > max_freq) { max_freq = value; } }); // Print the count document.write( max_freq );}// Driver Codevar arr = [5, 2, 6, 5, 2, 4, 5, 2];var N = arr.length;Maximum_subsequence(arr, N);// This code is contributed by itsok.</script> |
3
Time Complexity: O(N), since one traversal of the array is required to complete all operations.
Auxiliary Space: O(N), an unordered map is used and in the worst case, all elements will be stored inside it.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
