Longest sub | Function to return the length of the longest required sub - sequence ; Sort the array ; To store the resultant length ; If array contains only one element then it divides itself ; Every element divides itself ; Count for all numbers which are lesser than a [ i ] ; If a [ i ] % a [ j ] then update the maximum subsequence length , dp [ i ] = max ( dp [ i ] , 1 + dp [ j ] ) where j is in the range [ 0 , i - 1 ] ; If array contains only one element then i = j which doesn 't satisfy the condition ; Driver code
def find ( n , a ) : NEW_LINE INDENT a . sort ( ) ; NEW_LINE res = 1 ; NEW_LINE dp = [ 0 ] * n ; NEW_LINE dp [ 0 ] = 1 ; NEW_LINE for i in range ( 1 , n ) : NEW_LINE INDENT dp [ i ] = 1 ; NEW_LINE for j in range ( i ) : NEW_LINE INDENT if ( a [ i ] % a [ j ] == 0 ) : NEW_LINE INDENT dp [ i ] = max ( dp [ i ] , 1 + dp [ j ] ) ; NEW_LINE DEDENT DEDENT res = max ( res , dp [ i ] ) ; NEW_LINE DEDENT if ( res == 1 ) : NEW_LINE INDENT return - 1 NEW_LINE DEDENT else : NEW_LINE INDENT return res ; NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT a = [ 2 , 4 , 6 , 1 , 3 , 11 ] ; NEW_LINE n = len ( a ) ; NEW_LINE print ( find ( n , a ) ) ; NEW_LINE DEDENT