Largest divisible pairs subset | function to find the longest Subsequence ; dp [ i ] is going to store size of largest divisible subset beginning with a [ i ] . ; Since last element is largest , d [ n - 1 ] is 1 ; Fill values for smaller elements . ; Find all multiples of a [ i ] and consider the multiple that has largest subset beginning with it . ; Return maximum value from dp [ ] ; Driver Code
< ? php function largestSubset ( $ a , $ n ) { $ dp = array ( ) ; $ dp [ $ n - 1 ] = 1 ; for ( $ i = $ n - 2 ; $ i >= 0 ; $ i -- ) { $ mxm = 0 ; for ( $ j = $ i + 1 ; $ j < $ n ; $ j ++ ) if ( $ a [ $ j ] % $ a [ $ i ] == 0 or $ a [ $ i ] % $ a [ $ j ] == 0 ) $ mxm = max ( $ mxm , $ dp [ $ j ] ) ; $ dp [ $ i ] = 1 + $ mxm ; } return max ( $ dp ) ; } $ a = array ( 1 , 3 , 6 , 13 , 17 , 18 ) ; $ n = count ( $ a ) ; echo largestSubset ( $ a , $ n ) ; ? >