Length of the longest increasing subsequence such that no two adjacent elements are coprime | 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 ; 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
< ? php $ N = 100005 ; function LIS ( $ a , $ n ) { $ dp = array ( ) ; $ d = array ( ) ; $ ans = 0 ; for ( $ 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 ] ] = max ( $ dp [ $ a [ $ i ] ] , $ dp [ $ d [ $ j ] ] + 1 ) ; $ dp [ $ a [ $ i ] ] = max ( $ dp [ $ a [ $ i ] ] , $ dp [ $ d [ $ a [ $ i ] / $ j ] ] + 1 ) ; $ d [ $ j ] = $ a [ $ i ] ; $ d [ $ a [ $ i ] / $ j ] = $ a [ $ i ] ; } } $ ans = max ( $ ans , $ dp [ $ a [ $ i ] ] ) ; $ d [ $ a [ $ i ] ] = $ a [ $ i ] ; } return $ ans ; } $ a = array ( 1 , 2 , 3 , 4 , 5 , 6 ) ; $ n = sizeof ( $ a ) ; echo LIS ( $ a , $ n ) ; ? >