Dada una array, arr[] de tamaño N , la tarea es encontrar la longitud de la subsecuencia principal creciente más larga posible realizando las siguientes operaciones.
- Si arr[i] ya es un número primo , no es necesario actualizar arr[i] .
- Actualice arr[i] no primo al número primo más cercano menor que arr[i] .
- Actualice arr[i] no primo al número primo más cercano mayor que arr[i] .
Ejemplos:
Entrada: arr[] = {8, 6, 9, 2, 5}
Salida: 2
Explicación :
las posibles reorganizaciones de la array son: {{7, 5, 2, 5}, {7, 7, 2, 5}, {11, 5, 2, 5}, {1, 7, 2, 5}}.
Por lo tanto, la longitud de la subsecuencia prima creciente más larga = 2.Entrada: arr[] = {27, 38, 43, 68, 83, 12, 69, 12}
Salida: 5
Enfoque ingenuo: el enfoque más simple es actualizar todos los elementos de la array dada a su número primo más pequeño más cercano o a su número primo mayor más cercano y luego generar todas las subsecuencias posibles de la array dada e imprimir la longitud de la subsecuencia más larga que consiste en primo números en orden creciente.
Complejidad temporal: O(2 N )
Espacio auxiliar: O(N)
Enfoque eficiente: la idea es utilizar el enfoque de programación dinámica para optimizar el enfoque anterior. Este problema es una variación básica del problema de la subsecuencia principal creciente más larga (LIPS) . Siga los pasos a continuación para resolver el problema.
- Inicialice una array bidimensional , digamos dp[][] de tamaño N * 2 , donde dp[i][0] almacena la longitud de la subsecuencia principal creciente más larga eligiendo el número primo más cercano más pequeño que arr[i] en i th index y dp[i][1] almacena la longitud de la subsecuencia prima creciente más larga eligiendo el número primo más cercano mayor o igual que arr[i] en i th index. A continuación se muestra la relación de recurrencia:
- Si el número primo menor más cercano a arr[j] < el número primo menor más cercano a arr[i]: dp[i][0] = 1 + dp[j][0]
- Si el número primo más cercano es mayor o igual que arr[j] < el número primo más pequeño más cercano a arr[i]: dp[i][0] = max(dp[i][0], 1 + dp[j][1 ])
- Si el número primo menor más cercano a arr[j] < el número primo menor más cercano a arr[i]: dp[i][1] = 1 + dp[j][0]
- Si el número primo mayor o igual más cercano a arr[j] < el número primo más cercano mayor o igual a arr[i]: dp[i][1] = max(dp[i][1], 1 + dp[j] [1])
Aquí el valor de j = 0, 1, …, (i-1)
- Utilice la criba de Eratóstenes para calcular eficientemente los números primos .
- Recorra la array arr[] y para cada índice, i , actualice arr[i] al número primo más cercano de arr[i] .
- Para cada índice i , encuentre la longitud de la subsecuencia prima creciente más larga que termina en i , de manera óptima.
- Finalmente, devuelva la longitud de la subsecuencia prima creciente más larga.
A continuación se muestra la implementación del enfoque anterior:
Java
// Java Program to implement
// the above approach
import java.util.*;
public class Main {
// Stores the closest prime
// number for each array element
static TreeSet<Integer> set
= new TreeSet<>();
// Function to find the length of longest
// increasing prime subsequence
public static int LIPS(int arr[], int N)
{
// Base case
if (arr.length == 0)
return 0;
int dp[][] = new int[N + 1][2];
// Store the length of the longest
// increasing prime subsequence
int max_subsequence = 0;
for (int i = 0; i < arr.length;
i++) {
// Store the length of LIPS
// by choosing the closest prime
// number smaller than arr[i]
dp[i][0] = (arr[i] >= 2) ? 1 : 0;
// Store the length of longest LIPS
// by choosing the closest prime
// number greater than arr[i]
dp[i][1] = 1;
for (int j = 0; j < i; j++) {
// Store closest smaller
// prime number
Integer option1 = set.floor(arr[j]);
// Store closest prime number
// greater or equal
Integer option2 = set.ceiling(arr[j]);
// Recurrence relation
// Fill the value of dp[i][0]
if (option1 != null
&& option1 < set.floor(arr[i]))
dp[i][0]
= Math.max(dp[i][0], dp[j][0] + 1);
if (option2 != null
&& option2 < set.floor(arr[i]))
dp[i][0]
= Math.max(dp[i][0], dp[j][1] + 1);
// Fill the value of dp[i][1]
if (option1 != null
&& option1 < set.ceiling(arr[i]))
dp[i][1]
= Math.max(dp[i][0], dp[j][0] + 1);
if (option2 != null
&& option2 < set.ceiling(arr[i]))
dp[i][1]
= Math.max(dp[i][1], dp[j][1] + 1);
}
// Store the length of the longest
// increasing prime subsequence
max_subsequence
= Math.max(max_subsequence, dp[i][0]);
max_subsequence
= Math.max(max_subsequence, dp[i][1]);
}
return max_subsequence;
}
// Function to generate all prime numbers
public static void prime_sieve()
{
// Store all prime numbers
boolean primes[]
= new boolean[1000000 + 5];
// Consider all prime numbers
// to be true initially
Arrays.fill(primes, true);
// Mark 0 and 1 non-prime
primes[0] = primes[1] = false;
// Set all even numbers to
// non-prime
for (int i = 4; i <= 1000000;
i += 2)
primes[i] = false;
for (int i = 3; i <= 1000000;
i += 2) {
// If current element is prime
if (primes[i]) {
// Update all its multiples
// as non-prime
for (int j = 2 * i; j <= 1000000;
j += i)
primes[j] = false;
}
}
// Mark 2 as prime
set.add(2);
// Add all primes to the set
for (int i = 3; i <= 1000000;
i += 2)
if (primes[i])
set.add(i);
}
// Driver Code
public static void main(String args[])
{
int N = 6;
int arr[] = { 6, 7, 8, 9, 10, 11 };
prime_sieve();
System.out.println(LIPS(arr, N));
}
}
3
Complejidad temporal: O(N 2 logN)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por hemanthswarna1506 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA