Dada una array arr[] de tamaño N. La tarea es encontrar la longitud de la subsecuencia más larga de la array dada de modo que la secuencia sea estrictamente creciente y no haya dos elementos adyacentes coprimos.
Nota: Los elementos en la array dada están estrictamente en orden creciente (1 <= a[i] <= 10 5 )
Ejemplos:
Entrada: a[] = { 1, 2, 3, 4, 5, 6}
Salida: 3
Explicación: las subsecuencias posibles son {1}, {2}, {3}, {4}, {5}, {6 }, {2, 4}, {2, 4, 6}, {2, 6}, {4, 6}, {3, 6}.
La subsecuencia {2, 4, 6} tiene la longitud más larga.Entrada: a[] = { 1, 1, 1, 1}
Salida: 1
Enfoque : La idea principal es utilizar el concepto de programación dinámica . Definamos dp[x] como el valor máximo de la longitud de la subsecuencia cuyo último elemento es x, y definamos d[i] como el (valor máximo de dp[x] donde x es divisible por i).
Debemos calcular dp[x] en el orden creciente de x. El valor de dp[x] es (valor máximo de d[i] donde i es un divisor de x) + 1. Después de calcular dp[x], para cada divisor i de x, debemos actualizar d[i] también . Este algoritmo funciona en O(N*logN) porque la suma del número de los divisores de 1 a N es O(N*logN).
Nota : Hay una caja de esquina. Cuando el conjunto es {1}, debe generar 1.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find the length of the
// longest increasing sub sequence from the given array
// such that no two adjacent elements are co prime
#include <bits/stdc++.h>
using namespace std;
#define N 100005
// Function to find the length of the
// longest increasing sub sequence from the given array
// such that no two adjacent elements are co prime
int LIS(int a[], int n)
{
// To store dp and d value
int dp[N], d[N];
// To store required answer
int ans = 0;
// For all elements in the array
for (int i = 0; i < n; i++) {
// Initially answer is one
dp[a[i]] = 1;
// For all it's divisors
for (int j = 2; j * j <= a[i]; j++) {
if (a[i] % j == 0) {
// Update the dp value
dp[a[i]] = max(dp[a[i]], dp[d[j]] + 1);
dp[a[i]] = max(dp[a[i]], dp[d[a[i] / j]] + 1);
// Update the divisor value
d[j] = a[i];
d[a[i] / j] = a[i];
}
}
// Check for required answer
ans = max(ans, dp[a[i]]);
// Update divisor of a[i]
d[a[i]] = a[i];
}
// Return required answer
return ans;
}
// Driver code
int main()
{
int a[] = { 1, 2, 3, 4, 5, 6 };
int n = sizeof(a) / sizeof(a[0]);
cout << LIS(a, n);
return 0;
}
Java
// Java program to find the length
// of the longest increasing sub
// sequence from the given array
// such that no two adjacent
// elements are co prime
class GFG
{
static int N=100005;
// Function to find the length of the
// longest increasing sub sequence
// from the given array such that
// no two adjacent elements are co prime
static int LIS(int a[], int n)
{
// To store dp and d value
int dp[]=new int[N], d[]=new int[N];
// To store required answer
int ans = 0;
// For all elements in the array
for (int i = 0; i < n; i++)
{
// Initially answer is one
dp[a[i]] = 1;
// For all it's divisors
for (int j = 2; j * j <= a[i]; j++)
{
if (a[i] % j == 0)
{
// Update the dp value
dp[a[i]] = Math.max(dp[a[i]], dp[d[j]] + 1);
dp[a[i]] = Math.max(dp[a[i]], dp[d[a[i] / j]] + 1);
// Update the divisor value
d[j] = a[i];
d[a[i] / j] = a[i];
}
}
// Check for required answer
ans = Math.max(ans, dp[a[i]]);
// Update divisor of a[i]
d[a[i]] = a[i];
}
// Return required answer
return ans;
}
// Driver code
public static void main(String args[])
{
int a[] = { 1, 2, 3, 4, 5, 6 };
int n = a.length;
System.out.print( LIS(a, n));
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to find the length of the # longest increasing sub sequence from the # given array such that no two adjacent # elements are co prime N = 100005 # Function to find the length of the # longest increasing sub sequence from # the given array such that no two # adjacent elements are co prime def LIS(a, n): # To store dp and d value dp = [0 for i in range(N)] d = [0 for i in range(N)] # To store required answer ans = 0 # For all elements in the array for i in range(n): # Initially answer is one dp[a[i]] = 1 # For all it's divisors for j in range(2, a[i]): if j * j > a[i]: break if (a[i] % j == 0): # Update the dp value dp[a[i]] = max(dp[a[i]], dp[d[j]] + 1) dp[a[i]] = max(dp[a[i]], dp[d[a[i] // j]] + 1) # Update the divisor value d[j] = a[i] d[a[i] // j] = a[i] # Check for required answer ans = max(ans, dp[a[i]]) # Update divisor of a[i] d[a[i]] = a[i] # Return required answer return ans # Driver code a = [1, 2, 3, 4, 5, 6] n = len(a) print(LIS(a, n)) # This code is contributed by mohit kumar
C#
// C# program to find the length
// of the longest increasing sub
// sequence from the given array
// such that no two adjacent
// elements are co prime
using System;
class GFG
{
static int N = 100005;
// Function to find the length of the
// longest increasing sub sequence
// from the given array such that
// no two adjacent elements are co prime
static int LIS(int []a, int n)
{
// To store dp and d value
int []dp = new int[N];
int []d = new int[N];
// To store required answer
int ans = 0;
// For all elements in the array
for (int i = 0; i < n; i++)
{
// Initially answer is one
dp[a[i]] = 1;
// For all it's divisors
for (int j = 2; j * j <= a[i]; j++)
{
if (a[i] % j == 0)
{
// Update the dp value
dp[a[i]] = Math.Max(dp[a[i]], dp[d[j]] + 1);
dp[a[i]] = Math.Max(dp[a[i]], dp[d[a[i] / j]] + 1);
// Update the divisor value
d[j] = a[i];
d[a[i] / j] = a[i];
}
}
// Check for required answer
ans = Math.Max(ans, dp[a[i]]);
// Update divisor of a[i]
d[a[i]] = a[i];
}
// Return required answer
return ans;
}
// Driver code
public static void Main()
{
int []a = { 1, 2, 3, 4, 5, 6 };
int n = a.Length;
Console.WriteLine(LIS(a, n));
}
}
// This code is contributed by Ryuga
PHP
<?php
// PHP program to find the length of the
// longest increasing sub sequence from
// the given array such that no two adjacent
// elements are co prime
$N = 100005;
// Function to find the length of the
// longest increasing sub sequence from
// the given array such that no two
// adjacent elements are co prime
function LIS($a, $n)
{
// To store dp and d value
$dp = array();
$d = array();
// To store required answer
$ans = 0;
// For all elements in the array
for ($i = 0; $i < $n; $i++)
{
// Initially answer is one
$dp[$a[$i]] = 1;
// For all it's divisors
for ($j = 2; $j * $j <= $a[$i]; $j++)
{
if ($a[$i] % $j == 0)
{
// Update the dp value
$dp[$a[$i]] = max($dp[$a[$i]],
$dp[$d[$j]] + 1);
$dp[$a[$i]] = max($dp[$a[$i]],
$dp[$d[$a[$i] / $j]] + 1);
// Update the divisor value
$d[$j] = $a[$i];
$d[$a[$i] / $j] = $a[$i];
}
}
// Check for required answer
$ans = max($ans, $dp[$a[$i]]);
// Update divisor of a[i]
$d[$a[$i]] = $a[$i];
}
// Return required answer
return $ans;
}
// Driver code
$a = array(1, 2, 3, 4, 5, 6);
$n = sizeof($a);
echo LIS($a, $n);
// This code is contributed
// by Akanksha Rai
?>
Javascript
<script>
// Javascript program to find the length of the
// longest increasing sub sequence from
// the given array such that no two adjacent
// elements are co prime
let N = 100005;
// Function to find the length of the
// longest increasing sub sequence from
// the given array such that no two
// adjacent elements are co prime
function LIS(a, n)
{
// To store dp and d value
let dp = new Array();
let d = new Array();
// To store required answer
let ans = 0;
// For all elements in the array
for (let i = 0; i < n; i++)
{
// Initially answer is one
dp[a[i]] = 1;
// For all it's divisors
for (j = 2; j * j <= a[i]; j++)
{
if (a[i] % j == 0)
{
// Update the dp value
dp[a[i]] = Math.max(dp[a[i]],
dp[d[j]] + 1);
dp[a[i]] = Math.max(dp[a[i]],
dp[d[a[i] / j]] + 1);
// Update the divisor value
d[j] = a[i];
d[a[i] / j] = a[i];
}
}
// Check for required answer
ans = Math.max(ans, dp[a[i]]);
// Update divisor of a[i]
d[a[i]] = a[i];
}
// Return required answer
return ans;
}
// Driver code
let a = [1, 2, 3, 4, 5, 6];
let n = a.length;
document.write(LIS(a, n));
// This code is contributed
// by _saurabh_jaiswal
</script>
Producción:
3
Complejidad de tiempo: O(N* log(N))
Espacio Auxiliar: O(N), ya que se ha tomado N espacio extra.
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA