Par de subsecuencias de un arreglo dado que tiene todos los elementos únicos y todos iguales respectivamente

Dada una array arr[] de N enteros, la tarea es elegir las dos subsecuencias de igual longitud de manera que la primera subsecuencia debe tener todos los elementos únicos y la segunda subsecuencia debe tener todos los mismos elementos. Imprime la longitud máxima del par de subsecuencias.

Ejemplos:

Entrada: arr[] = {1, 2, 3, 1, 2, 3, 3, 3} 
Salida: 3 
Explicación: 
La primera subsecuencia consta de elementos {1, 2, 3}. 
La segunda subsecuencia consta de los elementos {3, 3, 3}.

Entrada: arr[] = {2, 2, 2, 3} 
Salida: 2 
Explicación: 
La primera subsecuencia consta de elementos {2, 3}. 
La segunda subsecuencia consta de los elementos {2, 2}.

Acercarse:

1. Cuente la frecuencia máxima (digamos f ) del elemento en la array dada.
2. Cuente los distintos elementos (digamos d ) presentes en la array.
3. Para hacer que ambas subsecuencias tengan la misma longitud con la propiedad dada, entonces el tamaño de la primera subsecuencia no puede exceder d , y el tamaño de la segunda subsecuencia no puede exceder f .
4. El valor máximo de la subsecuencia se da sobre la base de dos casos a continuación: 
   • La subsecuencia con elementos distintos debe tener un elemento con máxima frecuencia. Por lo tanto, el mínimo de (d, f – 1) es la longitud posible de una subsecuencia con la propiedad dada.
   • Si la longitud de una subsecuencia con un elemento distinto es mayor que la frecuencia máxima, entonces, el mínimo de (d – 1, f) es la longitud posible de una subsecuencia con la propiedad dada.
5. El valor máximo en los dos casos anteriores es la longitud máxima de una subsecuencia con la propiedad dada.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the maximum length
// of subsequences with given property
int maximumSubsequence(int arr[], int N)
{
    // To store the frequency
    unordered_map<int, int> M;
 
    // Traverse the array to store the
    // frequency
    for (int i = 0; i < N; i++) {
        M[arr[i]]++;
    }
 
    // M.size() given count of distinct
    // element in arr[]
    int distinct_size = M.size();
    int maxFreq = 1;
 
    // Traverse map to find max frequency
    for (auto& it : M) {
 
        maxFreq = max(maxFreq, it.second);
    }
 
    // Find the maximum length on the basis
    // of two cases in the approach
 
    cout << max(min(distinct_size, maxFreq - 1),
                min(distinct_size - 1, maxFreq));
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 3, 4, 4, 4, 4, 4, 5 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call
    maximumSubsequence(arr, N);
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to find the maximum length
// of subsequences with given property
static void maximumSubsequence(int arr[], int N)
{
     
    // To store the frequency
    HashMap<Integer,
            Integer> M = new HashMap<Integer,
                                     Integer>();
 
    // Traverse the array to store the
    // frequency
    for(int i = 0; i < N; i++)
    {
        if(M.containsKey(arr[i]))
        {
            M.put(arr[i], M.get(arr[i]) + 1);
        }
        else
        {
            M.put(arr[i], 1);
        }
    }
 
    // M.size() given count of distinct
    // element in arr[]
    int distinct_size = M.size();
    int maxFreq = 1;
 
    // Traverse map to find max frequency
    for(Map.Entry<Integer, Integer> it : M.entrySet())
    {
        maxFreq = Math.max(maxFreq, it.getValue());
    }
 
    // Find the maximum length on the basis
    // of two cases in the approach
 
    System.out.print(Math.max(
        Math.min(distinct_size, maxFreq - 1),
        Math.min(distinct_size - 1, maxFreq)));
}
 
// Driver Code
public static void main(String[] args)
{
    int arr[] = { 1, 2, 3, 4, 4, 4, 4, 4, 5 };
    int N = arr.length;
 
    // Function call
    maximumSubsequence(arr, N);
}
}
 
// This code is contributed by amal kumar choubey

# Python 3 program for the above approach
 
# Function to find the maximum length
# of subsequences with given property
def maximumSubsequence(arr, N):
     
    # To store the frequency
    M = {i : 0 for i in range(100)}
 
    # Traverse the array to store the
    # frequency
    for i in range(N):
        M[arr[i]] += 1
 
    # M.size() given count of distinct
    # element in arr[]
    distinct_size = len(M)
    maxFreq = 1
 
    # Traverse map to find max frequency
    for value in M.values():
        maxFreq = max(maxFreq, value)
 
    # Find the maximum length on the basis
    # of two cases in the approach
 
    print(max(min(distinct_size,  maxFreq - 1),
          min(distinct_size - 1, maxFreq)))
 
# Driver Code
if __name__ == '__main__':
     
    arr = [ 1, 2, 3, 4, 4, 4, 4, 5 ]
    N = len(arr)
 
    # Function call
    maximumSubsequence(arr, N)
 
# This code is contributed by Samarth

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
 
// Function to find the maximum length
// of subsequences with given property
static void maximumSubsequence(int []arr, int N)
{
     
    // To store the frequency
    Dictionary<int,
               int> M = new Dictionary<int,
                                       int>();
 
    // Traverse the array to store the
    // frequency
    for(int i = 0; i < N; i++)
    {
        if(M.ContainsKey(arr[i]))
        {
            M[arr[i]] =  M[arr[i]] + 1;
        }
        else
        {
            M.Add(arr[i], 1);
        }
    }
 
    // M.Count given count of distinct
    // element in []arr
    int distinct_size = M.Count;
    int maxFreq = 1;
 
    // Traverse map to find max frequency
    foreach(KeyValuePair<int, int> m in M)
    {
        maxFreq = Math.Max(maxFreq, m.Value);
    }
 
    // Find the maximum length on the basis
    // of two cases in the approach
 
    Console.Write(Math.Max(
        Math.Min(distinct_size, maxFreq - 1),
        Math.Min(distinct_size - 1, maxFreq)));
}
 
// Driver Code
public static void Main(String[] args)
{
    int []arr = { 1, 2, 3, 4, 4, 4, 4, 4, 5 };
    int N = arr.Length;
 
    // Function call
    maximumSubsequence(arr, N);
}
}
 
// This code is contributed by Rohit_ranjan

<script>
// Javascript program for the above approach
 
// Function to find the maximum length
// of subsequences with given property
function maximumSubsequence(arr, N) {
    // To store the frequency
    let M = new Map();
 
    // Traverse the array to store the
    // frequency
    for (let i = 0; i < N; i++) {
        if (M.has(arr[i])) {
            M.set(arr[i], M.get(arr[i]) + 1);
        }
        else {
            M.set(arr[i], 1);
        }
    }
 
    // M.size() given count of distinct
    // element in arr[]
    let distinct_size = M.size;
    let maxFreq = 1;
 
    // Traverse map to find max frequency
    for (let it of M) {
 
        maxFreq = Math.max(maxFreq, it[1]);
    }
 
    // Find the maximum length on the basis
    // of two cases in the approach
 
    document.write(Math.max(Math.min(distinct_size, maxFreq - 1), Math.min(distinct_size - 1, maxFreq)));
}
 
// Driver Code
 
let arr = [1, 2, 3, 4, 4, 4, 4, 4, 5];
let N = arr.length;
 
// Function call
maximumSubsequence(arr, N);
 
// This code is contributed by _saurabh_jaiswal
</script>

4

Complejidad de tiempo: O(N) , donde N es el número de elementos en la array. 
Complejidad del espacio auxiliar: O(N) , donde N es el número de elementos de la array.