Longitud de la subsecuencia creciente más larga tal que no hay dos elementos adyacentes coprimos

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:
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:

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *