Minimizar el número de subsecuencias estrictamente crecientes en una array | conjunto 2

Dada una array arr[] de tamaño N , la tarea es imprimir el recuento mínimo posible de subsecuencias estrictamente crecientes presentes en la array. 
Nota: es posible intercambiar los pares de elementos de array.

Ejemplos:

Entrada: arr[] = {2, 1, 2, 1, 4, 3}
Salida: 2
Explicación: Ordenar la array modifica la array a arr[] = {1, 1, 2, 2, 3, 4}. Dos posibles subsecuencias crecientes son {1, 2, 3} y {1, 2, 4}, que involucra a todos los elementos del arreglo.

Entrada: arr[] = {3, 3, 3}
Salida: 3

Enfoque basado en MultiSet : consulte la publicación anterior para resolver el problema usando Multiset para encontrar la subsecuencia decreciente más larga en la array . 
Tiempo Complejidad: O(N ² )
Espacio Auxiliar: O(N)

Enfoque optimizado para el espacio: la idea óptima se basa en la siguiente observación:

Dos elementos con el mismo valor no se pueden incluir en una sola subsecuencia, ya que no formarán una subsecuencia estrictamente creciente. 
Por lo tanto, para cada elemento de array distinto, cuente su frecuencia, digamos y . Por lo tanto, se requieren al menos y subsecuencias. 
Por lo tanto, la respuesta requerida es la frecuencia del elemento de array que aparece más.

Siga los pasos a continuación para resolver el problema:

1. Inicialice una variable, digamos count , para almacenar el recuento final de subsecuencias estrictamente crecientes.
2. Recorra la array arr[] y realice las siguientes observaciones: 
   • Inicialice dos variables, digamos X , para almacenar el elemento de array actual y freqX para almacenar la frecuencia del elemento de array actual.
   • Encuentre y almacene todas las ocurrencias del elemento actual en freqX .
   • Si la frecuencia del elemento actual es mayor que el recuento anterior, actualice el recuento .
3. Imprime el valor de cuenta .

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 number of strictly
// increasing subsequences in an array
int minimumIncreasingSubsequences(
    int arr[], int N)
{
    // Sort the array
    sort(arr, arr + N);
 
    // Stores final count
    // of subsequences
    int count = 0;
    int i = 0;
 
    // Traverse the array
    while (i < N) {
 
        // Stores current element
        int x = arr[i];
 
        // Stores frequency of
        // the current element
        int freqX = 0;
 
        // Count frequency of
        // the current element
        while (i < N && arr[i] == x) {
            freqX++;
            i++;
        }
 
        // If current element frequency
        // is greater than count
        count = max(count, freqX);
    }
 
    // Print the final count
    cout << count;
}
 
// Driver Code
int main()
{
    // Given array
    int arr[] = { 2, 1, 2, 1, 4, 3 };
 
    // Size of the array
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function call to find
    // the number of strictly
    // increasing subsequences
    minimumIncreasingSubsequences(arr, N);
}

// Java program to implement
// the above approach
import java.util.*;
class GFG
{
   
// Function to find the number of strictly
// increasing subsequences in an array
static void minimumIncreasingSubsequences(
    int arr[], int N)
{
   
    // Sort the array
    Arrays.sort(arr);
 
    // Stores final count
    // of subsequences
    int count = 0;
    int i = 0;
 
    // Traverse the array
    while (i < N)
    {
 
        // Stores current element
        int x = arr[i];
 
        // Stores frequency of
        // the current element
        int freqX = 0;
 
        // Count frequency of
        // the current element
        while (i < N && arr[i] == x)
        {
            freqX++;
            i++;
        }
 
        // If current element frequency
        // is greater than count
        count = Math.max(count, freqX);
    }
 
    // Print the final count
    System.out.print(count);
}
 
// Driver Code
public static void main(String args[])
{
    // Given array
    int arr[] = { 2, 1, 2, 1, 4, 3 };
 
    // Size of the array
    int N = arr.length;
 
    // Function call to find
    // the number of strictly
    // increasing subsequences
    minimumIncreasingSubsequences(arr, N);
}
}
 
// This code is contributed by splevel62.

# Python3 program to implement
# the above approach
 
# Function to find the number of strictly
# increasing subsequences in an array
def minimumIncreasingSubsequences(arr, N) :
 
    # Sort the array
    arr.sort()
  
    # Stores final count
    # of subsequences
    count = 0
    i = 0
  
    # Traverse the array
    while (i < N) :
  
        # Stores current element
        x = arr[i]
  
        # Stores frequency of
        # the current element
        freqX = 0
  
        # Count frequency of
        # the current element
        while (i < N and arr[i] == x) :
            freqX += 1
            i += 1
  
        # If current element frequency
        # is greater than count
        count = max(count, freqX)
  
    # Print the final count
    print(count)
 
# Given array
arr = [ 2, 1, 2, 1, 4, 3 ]
 
# Size of the array
N = len(arr)
 
# Function call to find
# the number of strictly
# increasing subsequences
minimumIncreasingSubsequences(arr, N)
 
# This code is contributed by divyesh072019.

// C# program to implement
// the above approach
using System;
 
public class GFG
{
   
// Function to find the number of strictly
// increasing subsequences in an array
static void minimumIncreasingSubsequences(
    int []arr, int N)
{
   
    // Sort the array
    Array.Sort(arr);
 
    // Stores readonly count
    // of subsequences
    int count = 0;
    int i = 0;
 
    // Traverse the array
    while (i < N)
    {
 
        // Stores current element
        int x = arr[i];
 
        // Stores frequency of
        // the current element
        int freqX = 0;
 
        // Count frequency of
        // the current element
        while (i < N && arr[i] == x)
        {
            freqX++;
            i++;
        }
 
        // If current element frequency
        // is greater than count
        count = Math.Max(count, freqX);
    }
 
    // Print the readonly count
    Console.Write(count);
}
 
// Driver Code
public static void Main(String []args)
{
   
    // Given array
    int []arr = { 2, 1, 2, 1, 4, 3 };
 
    // Size of the array
    int N = arr.Length;
 
    // Function call to find
    // the number of strictly
    // increasing subsequences
    minimumIncreasingSubsequences(arr, N);
}
}
 
// This code is contributed by 29AjayKumar

<script>
    // Javascript program to implement the above approach
     
    // Function to find the number of strictly
    // increasing subsequences in an array
    function minimumIncreasingSubsequences(arr, N)
    {
 
        // Sort the array
        arr.sort(function(a, b){return a - b});
 
        // Stores readonly count
        // of subsequences
        let count = 0;
        let i = 0;
 
        // Traverse the array
        while (i < N)
        {
 
            // Stores current element
            let x = arr[i];
 
            // Stores frequency of
            // the current element
            let freqX = 0;
 
            // Count frequency of
            // the current element
            while (i < N && arr[i] == x)
            {
                freqX++;
                i++;
            }
 
            // If current element frequency
            // is greater than count
            count = Math.max(count, freqX);
        }
 
        // Print the readonly count
        document.write(count);
    }
     
    // Given array
    let arr = [ 2, 1, 2, 1, 4, 3 ];
  
    // Size of the array
    let N = arr.length;
  
    // Function call to find
    // the number of strictly
    // increasing subsequences
    minimumIncreasingSubsequences(arr, N);
   
  // This code is contributed by suresh07.
</script>

2

Complejidad temporal: O(NlogN)
Espacio auxiliar: O(1)