Subsecuencia creciente más larga formada al concatenar una array consigo misma N veces

Dada una array arr[] de tamaño N , la tarea es encontrar la longitud de la subsecuencia creciente más larga en la array formada por la concatenación de arr[] consigo misma al final N veces.
Ejemplos: 
 

Entrada: arr[] = {3, 2, 1}, N = 3 
Salida: 3 
Explicación: 
la array formada por la concatenación: 
{3, 2, 1, 3, 2, 1, 3, 2, 1} 
La más larga la subsecuencia creciente que se puede formar a partir de esta array es de longitud 3, que es {1, 2, 3}

Entrada: N = 3 arr[] = {3, 1, 4} 
Salida:  
Explicación: 
La array formada por concatenación: 
{3, 1, 4, 3, 1, 4, 3, 1, 4} 
La subsecuencia creciente más larga que se puede formar a partir de esta array es de longitud 3 que es {1, 3, 4} 

Enfoque ingenuo: 
el enfoque básico para resolver este problema es crear la array final concatenando la array dada a sí misma N veces y luego encontrando la subsecuencia creciente más larga en ella. 
Tiempo Complejidad: O(N ² ) 
Espacio Auxiliar: O(N ² )

Enfoque eficiente: 
según el enfoque eficiente, cualquier elemento que esté presente en la subsecuencia creciente más larga puede estar presente solo una vez. Significa que la repetición de los elementos N veces no afectará la subsecuencia, pero se puede elegir cualquier elemento en cualquier momento. Por lo tanto, sería eficiente encontrar el subconjunto creciente más largo en la array de longitud N, que se puede encontrar encontrando todos los elementos únicos de la array. 
A continuación se muestra el algoritmo para el enfoque eficiente: 
Algoritmo: 

• Almacene los elementos únicos de la array en un mapa con (elemento, recuento) como el par (clave, valor).
• Para cada elemento de la array 
  • Si el elemento actual no está presente en el mapa, insértelo en el mapa, contando 1.
  • De lo contrario, incremente el recuento de los elementos de la array en la array.
• Encuentre la longitud del mapa que será la respuesta deseada.

Por ejemplo: 

Dado Array be – {4, 4, 1}
Creando el mapa de elementos únicos: {(4, 2), (1, 1)} 
Longitud del Mapa = 2 
Por lo tanto, la subsecuencia más larga requerida = 2

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

// C++ implementation to find the
// longest increasing subsequence
// in repeating element of array
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the LCS
int findLCS(int arr[], int n){
    unordered_map<int, int> mp;
     
    // Loop to create frequency array
    for (int i = 0; i < n; i++) {
        mp[arr[i]]++;
    }
    return mp.size();
}
 
// Driver code
int main()
{
    int n = 3;
    int arr[] = {3, 2, 1};
    cout<<findLCS(arr, n);
    return 0;
}

// Java implementation to find the
// longest increasing subsequence
// in repeating element of array
import java.util.*;
 
class GFG{
 
// Function to find the LCS
static int findLCS(int arr[], int n)
{
    HashMap<Integer,
            Integer> mp = new HashMap<Integer,
                                      Integer>();
     
    // Loop to create frequency array
    for(int i = 0; i < n; i++)
    {
       if(mp.containsKey(arr[i]))
       {
           mp.put(arr[i], mp.get(arr[i]) + 1);
       }
       else
       {
           mp.put(arr[i], 1);
       }
    }
    return mp.size();
}
 
// Driver code
public static void main(String[] args)
{
    int n = 3;
    int arr[] = { 3, 2, 1 };
     
    System.out.print(findLCS(arr, n));
}
}
 
// This code is contributed by amal kumar choubey

# Python3 implementation to find the
# longest increasing subsequence
# in repeating element of array
 
# Function to find the LCS
def findLCS(arr, n):
     
    mp = {}
 
    # Loop to create frequency array
    for i in range(n):
        if arr[i] in mp:
            mp[arr[i]] += 1
        else:
            mp[arr[i]] = 1
             
    return len(mp)
 
# Driver code
n = 3
arr = [ 3, 2, 1 ]
 
print(findLCS(arr, n))
 
# This code is contributed by ng24_7

// C# implementation to find the
// longest increasing subsequence
// in repeating element of array
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find the LCS
static int findLCS(int []arr, int n)
{
    Dictionary<int,
               int> mp = new Dictionary<int,
                                        int>();
     
    // Loop to create frequency array
    for(int i = 0; i < n; i++)
    {
       if(mp.ContainsKey(arr[i]))
       {
           mp[arr[i]] = mp[arr[i]] + 1;
       }
       else
       {
           mp.Add(arr[i], 1);
       }
    }
    return mp.Count;
}
 
// Driver code
public static void Main(String[] args)
{
    int n = 3;
    int []arr = { 3, 2, 1 };
     
    Console.Write(findLCS(arr, n));
}
}
 
// This code is contributed by amal kumar choubey

<script>
 
// Javascript implementation to find the
// longest increasing subsequence
// in repeating element of array
 
// Function to find the LCS
function findLCS(arr, n)
{
    let mp = new Map();
      
    // Loop to create frequency array
    for(let i = 0; i < n; i++)
    {
       if(mp.has(arr[i]) != 0)
       {
           mp.set(arr[i], mp.get(arr[i]) + 1);
       }
       else
       {
           mp.set(arr[i], 1);
       }
    }
    return mp.size;
}
       
// Driver code
     
      let n = 3;
    let arr = [ 3, 2, 1 ];
      
    document.write(findLCS(arr, n));
                                                                                 
</script>

Análisis de rendimiento: 

• Complejidad de tiempo: como en el enfoque anterior, solo hay un ciclo que toma tiempo O (N) en el peor de los casos, por lo tanto, la complejidad de tiempo será O (N) .
• Complejidad espacial: como en el enfoque anterior, se usa un mapa Hash que puede tomar espacio O (N) en el peor de los casos, por lo tanto, la complejidad espacial será O (N)