Dada uma array arr [] , a tarefa é reorganizar a array para gerar subsequências decrescentes máximas e imprimir a contagem do número máximo de subsequências possíveis de modo que cada elemento da array possa ser parte de uma única subsequência e o comprimento das subsequências precisa ser maximizado.

Exemplo:

Entrada: arr [] = {5, 2, 3, 4} 
Saída: 1 
Explicação: 
A array fornecida pode ser reorganizada para {5, 4, 3, 2}.
Uma vez que cada elemento ocorre apenas uma vez, a array reorganizada forma uma subsequência decrescente de comprimento máximo possível.

Entrada: arr [] = {5, 2, 6, 5, 2, 4, 5, 2} 
Saída: 3 
Explicação: 
A array fornecida pode ser reorganizada para {5, 2, 6, 5, 4, 2, 5, 2}
As 3 subseqüências decrescentes de comprimento máximo possível a partir da array dada são {6, 5, 4, 2}, {5, 2} e {5, 2}

Abordagem: 
para resolver o problema, não há necessidade de reorganizar o array fornecido. Uma vez que cada elemento pode fazer parte de uma única subsequência, o número de subsequências será igual à frequência do elemento mais frequente .
Siga as etapas abaixo para resolver o problema:

• Percorra a array e armazene a frequência de cada elemento da array em um Hashmap
• Agora, atravesse o HashMap para encontrar a frequência máxima de um elemento em uma array.
• Imprima a frequência máxima como a contagem das subsequências decrescentes máximas possíveis.

Abaixo está a implementação da abordagem acima:

// 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 conntributed by itsok.
</script>

3

Complexidade de tempo: O (N) 
Espaço auxiliar: O (N)