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
def largestSubset ( a , n ) : NEW_LINE INDENT dp = [ 0 for i in range ( n ) ] NEW_LINE dp [ n - 1 ] = 1 ; NEW_LINE for i in range ( n - 2 , - 1 , - 1 ) : NEW_LINE INDENT mxm = 0 ; NEW_LINE for j in range ( i + 1 , n ) : NEW_LINE INDENT if a [ j ] % a [ i ] == 0 or a [ i ] % a [ j ] == 0 : NEW_LINE INDENT mxm = max ( mxm , dp [ j ] ) NEW_LINE DEDENT DEDENT dp [ i ] = 1 + mxm NEW_LINE DEDENT return max ( dp ) NEW_LINE DEDENT a = [ 1 , 3 , 6 , 13 , 17 , 18 ] NEW_LINE n = len ( a ) NEW_LINE print ( largestSubset ( a , n ) ) NEW_LINE