Maximizar el recuento de subsecuencias decrecientes de la array dada

Dada una array arr[] , la tarea es reorganizar la array para generar el máximo de subsecuencias decrecientes e imprimir el recuento del número máximo de subsecuencias posible de modo que cada elemento de la array pueda ser parte de una sola subsecuencia y la longitud de las subsecuencias debe ser maximizado.

Ejemplo:

Entrada: arr[] = {5, 2, 3, 4} 
Salida: 1 
Explicación: 
La array dada se puede reorganizar a {5, 4, 3, 2}.
Dado que cada elemento ocurre solo una vez, la array reorganizada forma una subsecuencia decreciente de la máxima longitud posible.

Entrada: arr[] = {5, 2, 6, 5, 2, 4, 5, 2} 
Salida: 3 
Explicación: 
La array dada se puede reorganizar a {5, 2, 6, 5, 4, 2, 5, 2}.
Las 3 subsecuencias decrecientes de máxima longitud posible de la array dada son {6, 5, 4, 2}, {5, 2} y {5, 2}

Enfoque: 
para resolver el problema, no hay necesidad de reorganizar la array dada. Dado que todo elemento puede formar parte de una sola subsecuencia, el número de subsecuencias será igual a la frecuencia del elemento más frecuente .
Siga los pasos a continuación para resolver el problema:

• Recorra la array y almacene la frecuencia de cada elemento de la array en un Hashmap
• Ahora, recorra el HashMap para encontrar la frecuencia máxima de un elemento en una array.
• Imprime la frecuencia máxima como el recuento de las subsecuencias decrecientes máximas posibles.

A continuación se muestra la implementación del enfoque anterior:

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to count maximum subsequence
void 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 Code
int 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 program for rearrange array
// to generate maximum decreasing
// subsequences
import 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 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# program for rearrange array
// to generate maximum decreasing
// subsequences
using System;
using System.Collections.Generic;
 
class GFG{
     
// Function to count maximum subsequence
public 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 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);
}
}
 
// This code is contributed by Rajput-Ji

<script>
// Javascript Program to implement
// the above approach
 
// Function to count maximum subsequence
function 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 Code
var 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

Complejidad temporal: O(N) 
Espacio auxiliar: O(N)