Dada una array arr[], la tarea es maximizar la longitud de la subsecuencia creciente reemplazando los elementos por números primos mayores o menores que el elemento.
Ejemplos:
Entrada: arr[] = {4, 20, 6, 12}
Salida: 3
Explicación:
Modifique la array arr[] como {3, 19, 5, 11} para maximizar la respuesta,
donde {3, 5, 11} es la más larga subsecuencia creciente con longitud de 3.Entrada: arr[] = {30, 43, 42, 19}
Salida: 2
Explicación:
Modifique la array arr[] como {31, 43, 42, 19} para maximizar la respuesta,
donde {31, 43} es la subsecuencia creciente más larga con longitud de 2.
Enfoque: La idea es reemplazar cada elemento con un número primo más pequeño y el siguiente número primo y formar otra secuencia sobre la cual podemos aplicar el algoritmo estándar de subsecuencia creciente más larga . Mantener un número primo mayor antes del número primo menor garantiza que ambos no pueden existir en una secuencia creciente simultáneamente.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for above approach
#include<bits/stdc++.h>
using namespace std;
// Function to check if a
// number is prime or not
bool isprime(int n)
{
if (n < 2)
return false;
for(int i = 2; i * i <= n; i++)
if (n % i == 0)
return false;
return true;
}
// Function to find nearest
// greater prime of given number
int nextprime(int n)
{
while (!isprime(n))
n++;
return n;
}
// Function to find nearest
// smaller prime of given number
int prevprime(int n)
{
if (n < 2)
return 2;
while (!isprime(n))
n--;
return n;
}
// Function to return length of longest
// possible increasing subsequence
int longestSequence(vector<int> A)
{
// Length of given array
int n = A.size();
int M = 1;
// Stores increasing subsequence
vector<int> l;
// Insert first element prevprime
l.push_back(prevprime(A[0]));
// Traverse over the array
for(int i = 1; i < n; i++)
{
// Current element
int x = A[i];
// Check for contribution of
// nextprime and prevprime
// to the increasing subsequence
// calculated so far
for(int p :{ nextprime(x),
prevprime(x) })
{
int low = 0;
int high = M - 1;
// Reset first element of list,
// if p is less or equal
if (p <= l[0])
{
l[0] = p;
continue;
}
// Finding appropriate position
// of Current element in l
while (low < high)
{
int mid = (low + high + 1) / 2;
if (p > l[mid])
low = mid;
else
high = mid - 1;
}
// Update the calculated position
// with Current element
if (low + 1 < M)
l[low + 1] = p;
// Otherwise add current element
// in L and increase M
// as list size increases
else
{
l.push_back(p);
M++;
}
}
}
// Return M as length of possible
// longest increasing sequence
return M;
}
// Driver Code
int main()
{
vector<int> A = { 4, 20, 6, 12 };
// Function call
cout << (longestSequence(A));
}
// This code is contributed by mohit kumar 29
Java
// Java Program for above approach
import java.util.*;
import java.lang.*;
class GFG {
// Function to check if a
// number is prime or not
static boolean isprime(int n)
{
if (n < 2)
return false;
for (int i = 2; i * i <= n; i++)
if (n % i == 0)
return false;
return true;
}
// Function to find nearest
// greater prime of given number
static int nextprime(int n)
{
while (!isprime(n))
n++;
return n;
}
// Function to find nearest
// smaller prime of given number
static int prevprime(int n)
{
if (n < 2)
return 2;
while (!isprime(n))
n--;
return n;
}
// Function to return length of longest
// possible increasing subsequence
static int longestSequence(int[] A)
{
// Length of given array
int n = A.length;
int M = 1;
// Stores increasing subsequence
List<Integer> l
= new ArrayList<>();
// Insert first element prevprime
l.add(prevprime(A[0]));
// Traverse over the array
for (int i = 1; i < n; i++) {
// Current element
int x = A[i];
// Check for contribution of
// nextprime and prevprime
// to the increasing subsequence
// calculated so far
for (int p :
new int[] { nextprime(x),
prevprime(x) }) {
int low = 0;
int high = M - 1;
// Reset first element of list,
// if p is less or equal
if (p <= l.get(0)) {
l.set(0, p);
continue;
}
// Finding appropriate position
// of Current element in l
while (low < high) {
int mid = (low + high + 1) / 2;
if (p > l.get(mid))
low = mid;
else
high = mid - 1;
}
// Update the calculated position
// with Current element
if (low + 1 < M)
l.set(low + 1, p);
// Otherwise add current element
// in L and increase M
// as list size increases
else {
l.add(p);
M++;
}
}
}
// Return M as length of possible
// longest increasing sequence
return M;
}
// Driver Code
public static void main(String[] args)
{
int[] A = { 4, 20, 6, 12 };
// Function call
System.out.println(
longestSequence(A));
}
}
Python3
# Python3 Program for # the above approach #Function to check if a # number is prime or not def isprime(n): if (n < 2): return False i = 2 while i * i <= n: if (n % i == 0): return False i += 2 return True # Function to find nearest # greater prime of given number def nextprime(n): while (not isprime(n)): n += 1 return n # Function to find nearest # smaller prime of given number def prevprime(n): if (n < 2): return 2 while (not isprime(n)): n -= 1 return n # Function to return length of longest # possible increasing subsequence def longestSequence(A): # Length of given array n = len(A) M = 1 # Stores increasing subsequence l = [] # Insert first element prevprime l.append(prevprime(A[0])) # Traverse over the array for i in range (1, n): # Current element x = A[i] # Check for contribution of # nextprime and prevprime # to the increasing subsequence # calculated so far for p in [nextprime(x), prevprime(x)]: low = 0 high = M - 1 # Reset first element of list, # if p is less or equal if (p <= l[0]): l[0] = p continue # Finding appropriate position # of Current element in l while (low < high) : mid = (low + high + 1) // 2 if (p > l[mid]): low = mid else: high = mid - 1 # Update the calculated position # with Current element if (low + 1 < M): l[low + 1] = p # Otherwise add current element # in L and increase M # as list size increases else : l.append(p) M += 1 # Return M as length of possible # longest increasing sequence return M # Driver Code if __name__ == "__main__": A = [4, 20, 6, 12] # Function call print(longestSequence(A)) # This code is contributed by Chitranayal
C#
// C# Program for
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to check if a
// number is prime or not
static bool isprime(int n)
{
if (n < 2)
return false;
for (int i = 2; i * i <= n; i++)
if (n % i == 0)
return false;
return true;
}
// Function to find nearest
// greater prime of given number
static int nextprime(int n)
{
while (!isprime(n))
n++;
return n;
}
// Function to find nearest
// smaller prime of given number
static int prevprime(int n)
{
if (n < 2)
return 2;
while (!isprime(n))
n--;
return n;
}
// Function to return length of longest
// possible increasing subsequence
static int longestSequence(int[] A)
{
// Length of given array
int n = A.Length;
int M = 1;
// Stores increasing
// subsequence
List<int> l = new List<int>();
// Insert first element
// prevprime
l.Add(prevprime(A[0]));
// Traverse over the array
for (int i = 1; i < n; i++)
{
// Current element
int x = A[i];
// Check for contribution of
// nextprime and prevprime
// to the increasing subsequence
// calculated so far
foreach (int p in new int[] {nextprime(x),
prevprime(x)})
{
int low = 0;
int high = M - 1;
// Reset first element
// of list, if p is less
// or equal
if (p <= l[0])
{
l[0] = p;
continue;
}
// Finding appropriate position
// of Current element in l
while (low < high)
{
int mid = (low + high + 1) / 2;
if (p > l[mid])
low = mid;
else
high = mid - 1;
}
// Update the calculated position
// with Current element
if (low + 1 < M)
l[low + 1] = p;
// Otherwise add current element
// in L and increase M
// as list size increases
else
{
l.Add(p);
M++;
}
}
}
// Return M as length
// of possible longest
// increasing sequence
return M;
}
// Driver Code
public static void Main(String[] args)
{
int[] A = {4, 20, 6, 12};
// Function call
Console.WriteLine(longestSequence(A));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program for above approach
// Function to check if a
// number is prime or not
function isprime(n)
{
if (n < 2)
return false;
for(let i = 2; i * i <= n; i++)
if (n % i == 0)
return false;
return true;
}
// Function to find nearest
// greater prime of given number
function nextprime(n)
{
while (!isprime(n))
n++;
return n;
}
// Function to find nearest
// smaller prime of given number
function prevprime(n)
{
if (n < 2)
return 2;
while (!isprime(n))
n--;
return n;
}
// Function to return length of longest
// possible increasing subsequence
function longestSequence(A)
{
// Length of given array
let n = A.length;
let M = 1;
// Stores increasing subsequence
let l = new Array();
// Insert first element prevprime
l.push(prevprime(A[0]));
// Traverse over the array
for(let i = 1; i < n; i++)
{
// Current element
let x = A[i];
// Check for contribution of
// nextprime and prevprime
// to the increasing subsequence
// calculated so far
for(let p of [nextprime(x), prevprime(x)])
{
let low = 0;
let high = M - 1;
// Reset first element of list,
// if p is less or equal
if (p <= l[0])
{
l[0] = p;
continue;
}
// Finding appropriate position
// of Current element in l
while (low < high)
{
let mid = low + high + 1 / 2;
if (p > l[mid])
low = mid;
else
high = mid - 1;
}
// Update the calculated position
// with Current element
if (low + 1 < M)
l[low + 1] = p;
// Otherwise add current element
// in L and increase M
// as list size increases
else
{
l.push(p);
M++;
}
}
}
// Return M as length of possible
// longest increasing sequence
return M;
}
// Driver Code
let A = [ 4, 20, 6, 12 ];
// Function call
document.write(longestSequence(A));
// This code is contributed by gfgking
</script>
Producción:
3
Complejidad de tiempo: O(N×logN)
Espacio auxiliar: O(N)