Dada una array arr[] de N elementos y un entero positivo K tal que K ≤ N . La tarea es encontrar el número de subsecuencias de longitud máxima K , es decir, subsecuencias de longitud 0, 1, 2, …, K – 1, K que tienen todos los elementos distintos.
Ejemplos:
Entrada: arr[] = {2, 2, 3, 3, 5}, K = 2
Salida: 14
Todas las subsecuencias válidas son {}, {2}, {2}, {3}, {3}, {5 },
{2, 3}, {2, 3}, {2, 3}, {2, 3}, {2, 5}, {2, 5}, {3, 5} y {3, 5}.Entrada: arr[] = {1, 2, 3, 4, 4}, K = 4
Salida: 24
Acercarse:
- Ordene la array a[] si aún no está ordenada y en un vector arr[] almacene las frecuencias de cada elemento de la array original. Por ejemplo, si a[] = {2, 2, 3, 3, 5} entonces arr[] = {2, 2, 1} porque 2 está presente dos veces, 3 está presente dos veces y 5 solo una vez.
- Digamos que m es la longitud del vector arr[] . Entonces m será el número de elementos distintos. Puede haber subsecuencias de longitud máxima m sin repetición. Si m < k entonces no hay subsecuencia de longitud k . Entonces, declare n = mínimo (m, k) .
- Ahora aplique la programación dinámica. Cree una array bidimensional dp[n + 1][m + 1] tal que dp[i][j] almacenará el número de subsecuencias de longitud i cuyo primer elemento comienza después del j -ésimo elemento de arr[] . Por ejemplo, dp[1][1] = 3 porque significa el número
de subsecuencias de longitud 1 cuyo primer elemento comienza después del 1er elemento de arr[] que son {3}, {3}, {5}.- Inicializa la primera fila de dp[][] a 1 .
- Ejecute dos bucles de arriba a abajo y de derecha a izquierda dentro del bucle anterior.
- Si j > m – i eso significa que no puede haber tales secuencias debido a la falta de elementos. Entonces dp[i][j] = 0 .
- De lo contrario, dp[i][j] = dp[i][j + 1] + arr[j] * dp[i – 1][j + 1] ya que el número será el número de subsecuencias ya existentes de longitud i más el número de subsecuencias de longitud i – 1 multiplicado por arr[j] debido a la repetición.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Returns number of subsequences
// of maximum length k and
// contains no repeated element
int countSubSeq(int a[], int n, int k)
{
// Sort the array a[]
sort(a, a + n);
vector<int> arr;
// Store the frequencies of all the
// distinct element in the vector arr
for (int i = 0; i < n;) {
int count = 1, x = a[i];
i++;
while (i < n && a[i] == x) {
count++;
i++;
}
arr.push_back(count);
}
int m = arr.size();
n = min(m, k);
// count is the number
// of such subsequences
int count = 1;
// Create a 2-d array dp[n+1][m+1] to
// store the intermediate result
int dp[n + 1][m + 1];
// Initialize the first row to 1
for (int i = 0; i <= m; i++)
dp[0][i] = 1;
// Update the dp[][] array based
// on the recurrence relation
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 0; j--) {
if (j > m - i)
dp[i][j] = 0;
else {
dp[i][j] = dp[i][j + 1]
+ arr[j] * dp[i - 1][j + 1];
}
}
count = count + dp[i][0];
}
// Return the number of subsequences
return count;
}
// Driver code
int main()
{
int a[] = { 2, 2, 3, 3, 5 };
int n = sizeof(a) / sizeof(int);
int k = 3;
cout << countSubSeq(a, n, k);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Returns number of subsequences
// of maximum length k and
// contains no repeated element
static int countSubSeq(int a[], int n, int k)
{
// Sort the array a[]
Arrays.sort(a);
List<Integer> arr = new LinkedList<>();
// Store the frequencies of all the
// distinct element in the vector arr
for (int i = 0; i < n;)
{
int count = 1, x = a[i];
i++;
while (i < n && a[i] == x)
{
count++;
i++;
}
arr.add(count);
}
int m = arr.size();
n = Math.min(m, k);
// count is the number
// of such subsequences
int count = 1;
// Create a 2-d array dp[n+1][m+1] to
// store the intermediate result
int [][]dp = new int[n + 1][m + 1];
// Initialize the first row to 1
for (int i = 0; i <= m; i++)
dp[0][i] = 1;
// Update the dp[][] array based
// on the recurrence relation
for (int i = 1; i <= n; i++)
{
for (int j = m; j >= 0; j--)
{
if (j > m - i)
dp[i][j] = 0;
else
{
dp[i][j] = dp[i][j + 1] +
arr.get(j) *
dp[i - 1][j + 1];
}
}
count = count + dp[i][0];
}
// Return the number of subsequences
return count;
}
// Driver code
public static void main(String[] args)
{
int a[] = { 2, 2, 3, 3, 5 };
int n = a.length;
int k = 3;
System.out.println(countSubSeq(a, n, k));
}
}
// This code is contributed by PrinciRaj1992
Python 3
# Python 3 implementation of the approach # Returns number of subsequences # of maximum length k and # contains no repeated element def countSubSeq(a, n, k): # Sort the array a[] a.sort(reverse = False) arr = [] # Store the frequencies of all the # distinct element in the vector arr i = 0 while(i < n): count = 1 x = a[i] i += 1 while (i < n and a[i] == x): count += 1 i += 1 arr.append(count) m = len(arr) n = min(m, k) # count is the number # of such subsequences count = 1 # Create a 2-d array dp[n+1][m+1] to # store the intermediate result dp = [[0 for i in range(m + 1)] for j in range(n + 1)] # Initialize the first row to 1 for i in range(m + 1): dp[0][i] = 1 # Update the dp[][] array based # on the recurrence relation for i in range(1, n + 1, 1): j = m while(j >= 0): if (j > m - i): dp[i][j] = 0 else: dp[i][j] = dp[i][j + 1] + \ arr[j] * dp[i - 1][j + 1] j -= 1 count = count + dp[i][0] # Return the number of subsequences return count # Driver code if __name__ == '__main__': a = [2, 2, 3, 3, 5] n = len(a) k = 3 print(countSubSeq(a, n, k)) # This code is contributed by Surendra_Gangwar
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// Returns number of subsequences
// of maximum length k and
// contains no repeated element
static int countSubSeq(int []a, int n, int k)
{
// Sort the array a[]
Array.Sort(a);
List<int> arr = new List<int>();
int count, x;
// Store the frequencies of all the
// distinct element in the vector arr
for (int i = 0; i < n;)
{
count = 1;
x = a[i];
i++;
while (i < n && a[i] == x)
{
count++;
i++;
}
arr.Add(count);
}
int m = arr.Count;
n = Math.Min(m, k);
// count is the number
// of such subsequences
count = 1;
// Create a 2-d array dp[n+1][m+1] to
// store the intermediate result
int [,]dp = new int[n + 1, m + 1];
// Initialize the first row to 1
for (int i = 0; i <= m; i++)
dp[0, i] = 1;
// Update the dp[][] array based
// on the recurrence relation
for (int i = 1; i <= n; i++)
{
for (int j = m; j >= 0; j--)
{
if (j > m - i)
dp[i, j] = 0;
else
{
dp[i, j] = dp[i, j + 1] +
arr[j] *
dp[i - 1, j + 1];
}
}
count = count + dp[i, 0];
}
// Return the number of subsequences
return count;
}
// Driver code
public static void Main(String[] args)
{
int []a = { 2, 2, 3, 3, 5 };
int n = a.Length;
int k = 3;
Console.WriteLine(countSubSeq(a, n, k));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of the approach
// Returns number of subsequences
// of maximum length k and
// contains no repeated element
function countSubSeq(a, n, k)
{
// Sort the array a[]
a.sort();
var arr = [];
// Store the frequencies of all the
// distinct element in the vector arr
for (var i = 0; i < n;) {
var count = 1, x = a[i];
i++;
while (i < n && a[i] == x) {
count++;
i++;
}
arr.push(count);
}
var m = arr.length;
n = Math.min(m, k);
// count is the number
// of such subsequences
var count = 1;
// Create a 2-d array dp[n+1][m+1] to
// store the intermediate result
var dp = Array.from(Array(n+1), ()=>Array(m+1));
// Initialize the first row to 1
for (var i = 0; i <= m; i++)
dp[0][i] = 1;
// Update the dp[][] array based
// on the recurrence relation
for (var i = 1; i <= n; i++) {
for (var j = m; j >= 0; j--) {
if (j > m - i)
dp[i][j] = 0;
else {
dp[i][j] = dp[i][j + 1]
+ arr[j] * dp[i - 1][j + 1];
}
}
count = count + dp[i][0];
}
// Return the number of subsequences
return count;
}
// Driver code
var a = [2, 2, 3, 3, 5];
var n = a.length;
var k = 3;
document.write( countSubSeq(a, n, k));
</script>
Producción:
18
Complejidad de tiempo: O(n*log(n)+n*m) donde m es el tamaño de la array y n=min(m,k).
Espacio Auxiliar: O(n*m)
Publicación traducida automáticamente
Artículo escrito por kaustavbhattachaarya y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA