Largest divisible pairs subset | Java program to find the largest subset which was each pair is divisible . ; 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 to check the above function
import java . util . Arrays ; class GFG { static int largestSubset ( int [ ] a , int n ) { int [ ] dp = new int [ n ] ; dp [ n - 1 ] = 1 ; for ( int i = n - 2 ; i >= 0 ; i -- ) { int mxm = 0 ; for ( int j = i + 1 ; j < n ; j ++ ) { if ( a [ j ] % a [ i ] == 0 a [ i ] % a [ j ] == 0 ) { mxm = Math . max ( mxm , dp [ j ] ) ; } } dp [ i ] = 1 + mxm ; } return Arrays . stream ( dp ) . max ( ) . getAsInt ( ) ; } public static void main ( String [ ] args ) { int [ ] a = { 1 , 3 , 6 , 13 , 17 , 18 } ; int n = a . length ; System . out . println ( largestSubset ( a , n ) ) ; } }