Length of the longest increasing subsequence such that no two adjacent elements are coprime | 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 ; 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
N = 100005 NEW_LINE def LIS ( a , n ) : NEW_LINE INDENT dp = [ 0 for i in range ( N ) ] NEW_LINE d = [ 0 for i in range ( N ) ] NEW_LINE ans = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT dp [ a [ i ] ] = 1 NEW_LINE for j in range ( 2 , a [ i ] ) : NEW_LINE INDENT if j * j > a [ i ] : NEW_LINE INDENT break NEW_LINE DEDENT if ( a [ i ] % j == 0 ) : NEW_LINE INDENT dp [ a [ i ] ] = max ( dp [ a [ i ] ] , dp [ d [ j ] ] + 1 ) NEW_LINE dp [ a [ i ] ] = max ( dp [ a [ i ] ] , dp [ d [ a [ i ] // j ] ] + 1 ) NEW_LINE d [ j ] = a [ i ] NEW_LINE d [ a [ i ] // j ] = a [ i ] NEW_LINE DEDENT DEDENT ans = max ( ans , dp [ a [ i ] ] ) NEW_LINE d [ a [ i ] ] = a [ i ] NEW_LINE DEDENT return ans NEW_LINE DEDENT a = [ 1 , 2 , 3 , 4 , 5 , 6 ] NEW_LINE n = len ( a ) NEW_LINE print ( LIS ( a , n ) ) NEW_LINE