Subsecuencia de longitud máxima tal que los elementos adyacentes en la subsecuencia tienen un factor común

Dada una array arr[] , la tarea es encontrar la longitud máxima de una subsecuencia tal que los elementos adyacentes en la subsecuencia tengan un factor común. 

Ejemplos: 

Entrada: arr[] = { 13, 2, 8, 6, 3, 1, 9 } 
Salida: 5
Subsecuencia de longitud máxima con condiciones satisfechas: { 2, 8, 6, 3, 9 } 

Entrada: arr[] = { 12, 2, 8, 6, 3, 1, 9 } 
Salida: 6
Subsecuencia de longitud máxima con condiciones satisfechas: {12, 2, 8, 6, 3, 9 }

Entrada: arr[] = { 1, 2, 2, 3, 3, 1 } 
Salida: 2 

Enfoque: Un enfoque ingenuo es considerar todas las subsecuencias y verificar cada subsecuencia si satisface la condición. 
Una solución eficiente es utilizar la programación Dinámica . Sea dp[i] la longitud máxima de la subsecuencia incluyendo arr[i]. Entonces, la siguiente relación se cumple para todo primo p tal que p es un factor primo de arr[i]:

dp[i] = max(dp[i], 1 + dp[pos[p]]) 
where pos[p] gives the index of p in the array 
where it last occurred.

Explicación: Atraviesa la array. Para un elemento arr[i], hay 2 posibilidades. 

1. Si los factores primos de arr[i] han mostrado su primera aparición en el arreglo, entonces dp[i] = 1
2. Si los factores primos de arr[i] ya han ocurrido, entonces este elemento se puede agregar en la subsecuencia ya que hay un factor común. Por lo tanto, dp[i] = max(dp[i], 1 + dp[pos[p]]) donde p es el factor primo común y pos[p] es el último índice de p en la array.

A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation of the above approach
#include <bits/stdc++.h>
#define N 100005
#define MAX 10000002
 
using namespace std;
 
int lpd[MAX];
 
// Function to compute least
// prime divisor of i
void preCompute()
{
    memset(lpd, 0, sizeof(lpd));
    lpd[0] = lpd[1] = 1;
    for (int i = 2; i * i < MAX; i++)
    {
        for (int j = i * 2; j < MAX; j += i)
        {
            if (lpd[j] == 0)
            {
                lpd[j] = i;
            }
        }
    }
    for (int i = 2; i < MAX; i++)
    {
        if (lpd[i] == 0)
        {
            lpd[i] = i;
        }
    }
}
 
// Function that returns the maximum
// length subsequence such that
// adjacent elements have a common factor.
int maxLengthSubsequence(int arr[], int n)
{
    int dp[N];
    unordered_map<int, int> pos;
 
    // Initialize dp array with 1.
    for (int i = 0; i <= n; i++)
        dp[i] = 1;
 
    for (int i = 0; i <= n; i++)
    {
        while (arr[i] > 1)
        {
            int p = lpd[arr[i]];
            if (pos[p])
            {
                // p has appeared at least once.
                dp[i] = max(dp[i], 1 + dp[pos[p]]);
            }
 
            // Update latest occurrence of prime p.
            pos[p] = i;
            while (arr[i] % p == 0)
                arr[i] /= p;
        }
    }
 
    // Take maximum value as the answer.
    int ans = 1;
    for (int i = 0; i <= n; i++)
    {
        ans = max(ans, dp[i]);
    }
 
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = { 13, 2, 8, 6, 3, 1, 9 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    preCompute();
 
    cout << maxLengthSubsequence(arr, n);
    return 0;
}

# Python3 implementation of the
# above approach
import math as mt
 
N = 100005
MAX = 1000002
 
lpd = [0 for i in range(MAX)]
 
# to compute least prime divisor of i
 
 
def preCompute():
 
    lpd[0], lpd[1] = 1, 1
 
    for i in range(2, mt.ceil(mt.sqrt(MAX))):
        for j in range(2 * i, MAX, i):
            if (lpd[j] == 0):
                lpd[j] = i
 
    for i in range(2, MAX):
        if (lpd[i] == 0):
            lpd[i] = i
 
# Function that returns the maximum
# length subsequence such that
# adjacent elements have a common factor.
 
 
def maxLengthSubsequence(arr, n):
    dp = [1 for i in range(N + 1)]
 
    pos = dict()
 
    # Initialize dp array with 1.
    for i in range(0, n):
        while (arr[i] > 1):
            p = lpd[arr[i]]
            if (p in pos.keys()):
 
                # p has appeared at least once.
                dp[i] = max(dp[i], 1 + dp[pos[p]])
 
            # Update latest occurrence of prime p.
            pos[p] = i
            while (arr[i] % p == 0):
                arr[i] //= p
 
    # Take maximum value as the answer.
    ans = 1
    for i in range(0, n + 1):
        ans = max(ans, dp[i])
 
    return ans
 
 
# Driver code
arr = [13, 2, 8, 6, 3, 1, 9]
n = len(arr)
 
preCompute()
 
print(maxLengthSubsequence(arr, n))
 
# This code is contributed by Mohit Kumar

// Java implementation of the above approach
import java.util.*;
class GfG {
    static int N, MAX;
 
    // Check if UpperBound is
    // given for all test Cases
    // N = 100005 ;
    // MAX = 10000002;
    static int lpd[];
 
    // Function to compute least prime divisor
    // of i upto MAX element of the  input array
    // it will be space efficient
    // if more test cases are there it's
    // better to find prime divisor
    // upto upperbound of input element
    // it will be cost efficient
    static void preCompute()
    {
        lpd = new int[MAX + 1];
        lpd[0] = lpd[1] = 1;
        for (int i = 2; i * i <= MAX; i++)
        {
            for (int j = i * 2; j <= MAX; j += i)
            {
                if (lpd[j] == 0)
                {
                    lpd[j] = i;
                }
            }
        }
        for (int i = 2; i <= MAX; i++)
        {
            if (lpd[i] == 0)
            {
                lpd[i] = i;
            }
        }
    }
 
    // Function that returns the maximum
    // length subsequence such that
    // adjacent elements have a common factor.
    static int maxLengthSubsequence(Integer arr[], int n)
    {
        Integer dp[] = new Integer[N];
        Map<Integer, Integer> pos
            = new HashMap<Integer, Integer>();
 
        // Initialize dp array with 1.
        for (int i = 0; i <= n; i++)
            dp[i] = 1;
 
        for (int i = 0; i <= n; i++)
        {
            while (arr[i] > 1) {
                int p = lpd[arr[i]];
                if (pos.containsKey(p))
                {
                    // p has appeared at least once.
                    dp[i] = Math.max(dp[i],
                                     1 + dp[pos.get(p)]);
                }
 
                // Update latest occurrence of prime p.
                pos.put(p, i);
                while (arr[i] % p == 0)
                    arr[i] /= p;
            }
        }
 
        // Take maximum value as the answer.
        int ans = Collections.max(Arrays.asList(dp));
        return ans;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        Integer arr[] = { 12, 2, 8, 6, 3, 1, 9 };
        N = arr.length;
        MAX = Collections.max(Arrays.asList(arr));
        preCompute();
        System.out.println(
            maxLengthSubsequence(arr, N - 1));
    }
}
 
// This code is contributed by Prerna Saini.

// C# implementation of the
// above approach
using System;
using System.Collections;
 
class GFG {
 
    static int N = 100005;
    static int MAX = 10000002;
 
    static int[] lpd = new int[MAX];
 
    // to compute least prime divisor of i
    static void preCompute()
    {
        lpd[0] = lpd[1] = 1;
        for (int i = 2; i * i < MAX; i++)
        {
            for (int j = i * 2; j < MAX; j += i)
            {
                if (lpd[j] == 0)
                {
                    lpd[j] = i;
                }
            }
        }
        for (int i = 2; i < MAX; i++)
        {
            if (lpd[i] == 0)
            {
                lpd[i] = i;
            }
        }
    }
 
    // Function that returns the maximum
    // length subsequence such that
    // adjacent elements have a common factor.
    static int maxLengthSubsequence(int[] arr, int n)
    {
        int[] dp = new int[N];
        Hashtable pos = new Hashtable();
 
        // Initialize dp array with 1.
        for (int i = 0; i <= n; i++)
            dp[i] = 1;
 
        for (int i = 0; i <= n; i++)
        {
            while (arr[i] > 1) {
                int p = lpd[arr[i]];
                if (pos.ContainsKey(p))
                {
                    // p has appeared at least once.
                    dp[i] = Math.Max(
                        dp[i],
                        1 + dp[Convert.ToInt32(pos[p])]);
                }
 
                // Update latest occurrence of prime p.
                pos[p] = i;
                while (arr[i] % p == 0)
                    arr[i] /= p;
            }
        }
 
        // Take maximum value as the answer.
        int ans = 1;
        for (int i = 0; i <= n; i++)
        {
            ans = Math.Max(ans, dp[i]);
        }
 
        return ans;
    }
 
    // Driver code
    public static void Main()
    {
        int[] arr = { 13, 2, 8, 6, 3, 1, 9 };
        int n = arr.Length - 1;
 
        preCompute();
        Console.WriteLine(maxLengthSubsequence(arr, n));
    }
}
 
// This code is contributed by Ryuga

<script>
 
// JavaScript implementation of the above approach   
     
    let N, MAX;
    // Check if UpperBound is
    // given for all test Cases
    // N = 100005 ;
    // MAX = 10000002;
    let  lpd;
     
    // Function to compute least prime divisor
    // of i upto MAX element of the  input array
    // it will be space efficient
    // if more test cases are there it's
    // better to find prime divisor
    // upto upperbound of input element
    // it will be cost efficient
    function preCompute()
    {
        lpd = new Array(MAX + 1);
        for(let i=0;i<lpd.length;i++)
        {
            lpd[i]=0;
        }
        lpd[0] = lpd[1] = 1;
        for (let i = 2; i * i <= MAX; i++)
        {
            for (let j = i * 2; j <= MAX; j += i)
            {
                if (lpd[j] == 0)
                {
                    lpd[j] = i;
                }
            }
        }
        for (let i = 2; i <= MAX; i++)
        {
            if (lpd[i] == 0)
            {
                lpd[i] = i;
            }
        }
    }
     
    // Function that returns the maximum
    // length subsequence such that
    // adjacent elements have a common factor.
    function maxLengthSubsequence(arr,n)
    {
        let dp = new Array(N);
        let pos
            = new Map();
  
        // Initialize dp array with 1.
        for (let i = 0; i <= n; i++)
            dp[i] = 1;
  
        for (let i = 0; i <= n; i++)
        {
            while (arr[i] > 1) {
                let p = lpd[arr[i]];
                if (pos.has(p))
                {
                    // p has appeared at least once.
                    dp[i] = Math.max(dp[i],
                                     1 + dp[pos.get(p)]);
                }
  
                // Update latest occurrence of prime p.
                pos.set(p, i);
                while (arr[i] % p == 0)
                    arr[i] = Math.floor(arr[i]/p);
            }
        }
  
        // Take maximum value as the answer.
        let ans = Math.max(...dp);
        return ans;
    }
     
    // Driver code
    let arr=[13, 2, 8, 6, 3, 1, 9 ];
    N = arr.length;
    MAX = Math.max(...arr);
    preCompute();
    document.write(maxLengthSubsequence(arr, N - 1));
 
 
 
// This code is contributed by patel2127
 
</script>

5

Complejidad de tiempo: O(N* log(N))
Espacio auxiliar: O(N)