Find the Largest divisor Subset in the Array | Function to find the required subsequence ; Sort the array ; Keep a count of the length of the subsequence and the previous element Set the initial values ; Maximum length of the subsequence and the last element ; Run a loop for every element ; Check for all the divisors ; If the element is a divisor and the length of subsequence will increase by adding j as previous element of i ; Increase the count ; Update the max count ; Get the last index of the subsequence ; Print the element ; Move the index to the previous element ; Driver code
def findSubSeq ( arr , n ) : NEW_LINE INDENT arr . sort ( ) ; NEW_LINE count = [ 1 ] * n ; NEW_LINE prev = [ - 1 ] * n ; NEW_LINE max = 0 ; NEW_LINE maxprev = - 1 ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( i - 1 , - 1 , - 1 ) : NEW_LINE INDENT if ( arr [ i ] % arr [ j ] == 0 and count [ j ] + 1 > count [ i ] ) : NEW_LINE INDENT count [ i ] = count [ j ] + 1 ; NEW_LINE prev [ i ] = j ; NEW_LINE DEDENT DEDENT if ( max < count [ i ] ) : NEW_LINE INDENT max = count [ i ] ; NEW_LINE maxprev = i ; NEW_LINE DEDENT DEDENT i = maxprev ; NEW_LINE while ( i >= 0 ) : NEW_LINE INDENT if ( arr [ i ] != - 1 ) : NEW_LINE INDENT print ( arr [ i ] , end = " ▁ " ) ; NEW_LINE DEDENT i = prev [ i ] ; NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT arr = [ 1 , 2 , 3 , 4 , 5 ] ; NEW_LINE n = len ( arr ) ; NEW_LINE findSubSeq ( arr , n ) ; NEW_LINE DEDENT