Dada una array A[] de tamaño n donde solo hay elementos únicos en la array. Tenemos que encontrar la concatenación mínima requerida para que la secuencia A obtenga estrictamente la subsecuencia creciente más larga. Para la array A[] seguimos la indexación basada en 1.
Ejemplos:
Entrada: A = {1, 3, 2}
Salida: 2
Explicación:
Podemos concatenar A dos veces como [1, 3, 2, 1, 3, 2] y luego generar el índice 1, 3, 5 que da sub- secuencia como 1->2->3.
Entrada: A = {2, 1, 4, 3, 5}
Salida: 3
Explicación:
La array dada debe concatenarse 3 veces para generar la subsecuencia creciente más larga.
Enfoque:
Para resolver el problema mencionado anteriormente, la primera observación es que una subsecuencia estrictamente creciente siempre tendrá una longitud igual al número de elementos únicos presentes en la secuencia A[]. Por lo tanto, tenemos que encontrar una manera de mantener juntos el máximo de números consecutivos. Podemos lograr esto tomando tantos números estrictamente consecutivos en una secuencia antes de optar por la concatenación y manejar otros en la siguiente concatenación.
- Forme pares de elementos y su índice y guárdelos en orden según el valor. Inicialice una variable para contar las operaciones de concatenación requeridas.
- Ejecute un bucle desde el índice 2 hasta el índice n y si el índice del par [i-1] > par [i], incremente la variable en 1 que estaba contando las operaciones de concatenación requeridas; de lo contrario, continúe con el proceso.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP implementation to Find the minimum
// concatenation required to get strictly
// Longest Increasing Subsequence for the
// given array
#include <bits/stdc++.h>
using namespace std;
int increasingSubseq(int a[], int n)
{
// Ordered map containing pairs
// of value and index.
map<int, int> mp;
for (int i = 0; i < n; i++) {
// Form pairs of value at index i
// and it's index that is i.
mp.insert(make_pair(a[i], i));
}
// Variable to insert the minimum
// concatenations that are needed
int ans = 1;
// Iterator pointing to the
// second pair in the map
auto itr = ++mp.begin();
// Iterator pointing to the
// first pair in the map
for (auto it = mp.begin(); it != mp.end(); ++it) {
// Check if itr tends to end of map
if (itr != mp.end()) {
// Check if index2 is not greater than index1
// then we have to perform a concatenation.
if (itr->second <= it->second)
ans += 1;
++itr;
}
}
// Return the final answer
cout << ans << endl;
}
// Driver code
int main()
{
int a[] = { 2, 1, 4, 3, 5 };
int n = sizeof(a) / sizeof(a[0]);
increasingSubseq(a, n);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.util.*;
import java.io.*;
class GFG {
private static void increasingSubseq(int a[], int n)
{
// Ordered map containing pairs
// of value and index.
TreeMap<Integer, Integer> mp
= new TreeMap<Integer, Integer>();
for (int i = 0; i < n; i++) {
// Form pairs of value at index i
// and it's index that is i.
mp.put(a[i], i);
}
// Variable to insert the minimum
// concatenations that are needed
int ans = 1;
// Iterator pointing to the
// first entry in the map
Map.Entry<Integer, Integer> itr
= mp.pollFirstEntry();
for (Map.Entry<Integer, Integer> it :
mp.entrySet())
{
// Check if index2 is not greater than index1
// then we have to perform a concatenation.
if (itr.getValue() >= it.getValue())
ans++;
itr = it;
}
System.out.println(ans);
}
// Driver Code
public static void main(String[] args)
{
int a[] = { 2, 1, 4, 3, 5 };
int n = a.length;
increasingSubseq(a, n);
}
}
Python3
# Python 3 implementation to
# Find the minimum concatenation
# required to get strictly Longest
# Increasing Subsequence for the
# given array
def increasingSubseq(a, n):
# Ordered map containing pairs
# of value and index.
mp = {}
for i in range(n):
# Form pairs of value at
# index i and it's index
# that is i.
mp[a[i]] = i
# Variable to insert the
# minimum concatenations
# that are needed
ans = 1
# Iterator pointing to the
# second pair in the map
itr = 1
li= list(mp.values())
# Iterator pointing to the
# first pair in the map
for key, value in mp.items():
# Check if itr tends to
# end of map
if (itr < len(mp)):
# Check if index2 is not
# greater than index1
# then we have to perform
# a concatenation.
if (li[itr] <= key):
ans += 1
itr+=1
# Return the final
# answer
print(ans)
# Driver code
if __name__ == '__main__':
a = [2, 1, 4, 3, 5]
n = len(a)
increasingSubseq(a, n)
# This code is contributed by bgangwar59
Javascript
<script>
// Python 3 implementation to
// Find the minimum concatenation
// required to get strictly Longest
// Increasing Subsequence for the
// given array
function increasingSubseq(a, n){
// Ordered map containing pairs
// of value and index.
let mp = new Map()
for(let i=0;i<n;i++){
// Form pairs of value at
// index i and it's index
// that is i.
mp.set(a[i],i)
}
// Variable to insert the
// minimum concatenations
// that are needed
let ans = 1
// Iterator pointing to the
// second pair in the map
let itr = 1
let li= Array.from(mp.values())
// Iterator pointing to the
// first pair in the map
for([key, value] of mp){
// Check if itr tends to
// end of map
if (itr < mp.size){
// Check if index2 is not
// greater than index1
// then we have to perform
// a concatenation.
if (li[itr] <= key)
ans += 1
itr+=1
}
}
// Return the final
// answer
document.write(ans)
}
// Driver code
let a = [2, 1, 4, 3, 5]
let n = a.length
increasingSubseq(a, n)
// This code is contributed by shinjanpatra
</script>
3
Complejidad del tiempo: O(N * log N)