Dada una array A[] de tamaño n donde puede haber elementos repetitivos 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 = {2, 1, 2, 4, 3, 5}
Salida: 2
Explicación:
Podemos concatenar A dos veces como [2, 1, 2, 4, 3, 5, 2, 1, 2, 4, 3, 5] y luego salida para el índice 2, 3, 5, 10, 12 que da una subsecuencia como 1 -> 2 -> 3 -> 4 -> 5.Entrada: A = {1, 3, 2, 1, 2}
Salida: 2
Explicación:
Podemos concatenar A dos veces como [1, 3, 2, 1, 2, 1, 3, 2, 1, 2] y luego salida para el índice 1, 3, 7 que da una subsecuencia como 1 -> 2 -> 3.
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, la longitud máxima de la subsecuencia es igual a la cuenta de los distintos elementos. Para resolver el problema, siga los pasos que se detallan a continuación:
- Inicialice una variable, digamos ans a 1 y divida la secuencia en dos mitades, la subsecuencia izquierda y la derecha. Inicialice el leftSeq a NULL y copie la secuencia original en el rightSeq.
- Recorra la subsecuencia derecha para encontrar el elemento mínimo , representado por la variable CurrElement y almacene su índice.
- Ahora actualice la subsecuencia izquierda y derecha , donde leftSeq se actualiza con la secuencia dada hasta el índice que almacena el elemento mínimo en la subsecuencia derecha. Y el rightSeq a la secuencia dada desde el valor de índice mínimo hasta el final.
- Recorra la array para obtener el siguiente elemento mínimo y actualice el valor de CurrElement. Si no hay tal valor mínimo en rightSeq entonces tiene que estar en leftSeq. Encuentre el índice de ese elemento en la subsecuencia izquierda y almacene su índice.
- Ahora , vuelva a actualizar el valor de la subsecuencia izquierda y derecha, donde leftSeq = secuencia dada hasta el k-ésimo índice y rightSeq = secuencia dada desde el k-ésimo índice hasta el final. Repita el proceso hasta alcanzar el límite de la array.
- Incremente el valor de ans en 1 y deténgase cuando CurrElement sea igual al elemento más alto.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to Find the minimum
// concatenation required to get strictly
// Longest Increasing Subsequence for the
// given array with repetitive elements
#include <bits/stdc++.h>
using namespace std;
int LIS(int arr[], int n)
{
// ordered map containing value and
// a vector containing index of
// it's occurrences
map<int, vector<int> > m;
// Mapping index with their values
// in ordered map
for (int i = 0; i < n; i++)
m[arr[i]].push_back(i);
// k refers to present minimum index
int k = n;
// Stores the number of concatenation
// required
int ans = 0;
// Iterate over map m
for (auto it = m.begin(); it != m.end();
it++) {
// it.second refers to the vector
// containing all corresponding
// indexes
// it.second.back refers to the
// last element of corresponding vector
if (it->second.back() < k) {
k = it->second[0];
ans += 1;
}
else
// find the index of next minimum
// element in the sequence
k = *lower_bound(it->second.begin(),
it->second.end(), k);
}
// Return the final answer
cout << ans << endl;
}
// Driver program
int main()
{
int arr[] = { 1, 3, 2, 1, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
LIS(arr, n);
return 0;
}
Java
// Java implementation to Find the minimum
// concatenation required to get strictly
// Longest Increasing Subsequence for the
// given array with repetitive elements
import java.io.*;
import java.util.*;
class GFG{
static void LIS(int arr[], int n)
{
// ordered map containing value and
// a vector containing index of
// it's occurrences
TreeMap<Integer,
List<Integer>> m = new TreeMap<Integer,
List<Integer>>();
// Mapping index with their values
// in ordered map
for(int i = 0; i < n; i++)
{
List<Integer> indexes;
if (m.containsKey(arr[i]))
{
indexes = m.get(arr[i]);
}
else
{
indexes = new ArrayList<Integer>();
}
indexes.add(i);
m.put(arr[i], indexes);
}
// k refers to present minimum index
int k = n;
// Stores the number of concatenation
// required
int ans = 0;
// Iterate over map m
for(Map.Entry<Integer,
List<Integer>> it : m.entrySet())
{
// List containing all corresponding
// indexes
List<Integer> indexes = it.getValue();
if (indexes.get(indexes.size() - 1) < k)
{
k = indexes.get(0);
ans++;
}
else
// Find the index of next minimum
// element in the sequence
k = lower_bound(indexes, k);
}
// Return the final answer
System.out.println(ans);
}
static int lower_bound(List<Integer> indexes,
int k)
{
int low = 0, high = indexes.size() - 1;
while (low < high)
{
int mid = (low + high) / 2;
if (indexes.get(mid) < k)
low = mid + 1;
else
high = mid;
}
return indexes.get(low);
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 3, 2, 1, 2 };
int n = arr.length;
LIS(arr, n);
}
}
// This code is contributed by jithin
Python3
# Python3 implementation to
# Find the minimum concatenation
# required to get strictly Longest
# Increasing Subsequence for the
# given array with repetitive elements
from bisect import bisect_left
def LIS(arr, n):
# ordered map containing
# value and a vector containing
# index of it's occurrences
# <int, vector<int> > m;
m = {}
# Mapping index with their
# values in ordered map
for i in range(n):
m[arr[i]] = m.get(arr[i], [])
m[arr[i]].append(i)
# k refers to present
# minimum index
k = n
# Stores the number of
# concatenation required
ans = 1
# Iterate over map m
for key, value in m.items():
# it.second refers to the
# vector containing all
# corresponding indexes
# it.second.back refers
# to the last element of
# corresponding vector
if (value[len(value) - 1] < k):
k = value[0]
ans += 1
else:
# find the index of next
# minimum element in the
# sequence
k = bisect_left(value, k)
# Return the final
# answer
print(ans)
# Driver code
if __name__ == '__main__':
arr = [1, 3, 2, 1, 2]
n = len(arr)
LIS(arr, n)
# This code is contributed by bgangwar59
Producción:
2
Complejidad del tiempo: O(n * log n)