Find the Largest divisor Subset in the Array | Java implementation of the approach ; 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
import java . util . * ; class GFG { static void findSubSeq ( int arr [ ] , int n ) { Arrays . sort ( arr ) ; int count [ ] = new int [ n ] ; int prev [ ] = new int [ n ] ; int i , j ; for ( i = 0 ; i < n ; i ++ ) count [ i ] = 1 ; for ( j = 0 ; j < n ; j ++ ) prev [ j ] = - 1 ; int max = 0 ; int maxprev = - 1 ; for ( i = 0 ; i < n ; i ++ ) { for ( j = i - 1 ; j >= 0 ; j -- ) { if ( arr [ i ] % arr [ j ] == 0 && count [ j ] + 1 > count [ i ] ) { count [ i ] = count [ j ] + 1 ; prev [ i ] = j ; } } if ( max < count [ i ] ) { max = count [ i ] ; maxprev = i ; } } i = maxprev ; while ( i >= 0 ) { if ( arr [ i ] != - 1 ) System . out . print ( arr [ i ] + " ▁ " ) ; i = prev [ i ] ; } } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 2 , 3 , 4 , 5 } ; int n = arr . length ; findSubSeq ( arr , n ) ; } }