Length of the longest increasing subsequence such that no two adjacent elements are coprime | 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 ; Function to find the length of the longest increasing sub sequence from the given array such that no two adjacent elements are co prime ; To store dp and d value ; To store required answer ; For all elements in the array ; Initially answer is one ; For all it 's divisors ; Update the dp value ; Update the divisor value ; Check for required answer ; Update divisor of a [ i ] ; Return required answer ; Driver code
let N = 100005 ; function LIS ( a , n ) { let dp = new Array ( ) ; let d = new Array ( ) ; let ans = 0 ; for ( let i = 0 ; i < n ; i ++ ) { dp [ a [ i ] ] = 1 ; for ( j = 2 ; j * j <= a [ i ] ; j ++ ) { if ( a [ i ] % j == 0 ) { 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 ) ; d [ j ] = a [ i ] ; d [ a [ i ] / j ] = a [ i ] ; } } ans = Math . max ( ans , dp [ a [ i ] ] ) ; d [ a [ i ] ] = a [ i ] ; } return ans ; } let a = [ 1 , 2 , 3 , 4 , 5 , 6 ] ; let n = a . length ; document . write ( LIS ( a , n ) ) ;