Longest sub | Java implementation of the approach ; 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 ] = Math . 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
import java . util . Arrays ; import java . io . * ; class GFG { static int find ( int n , int a [ ] ) { Arrays . sort ( a ) ; int res = 1 ; int dp [ ] = new int [ n ] ; dp [ 0 ] = 1 ; for ( int i = 1 ; i < n ; i ++ ) { dp [ i ] = 1 ; for ( int j = 0 ; j < i ; j ++ ) { if ( a [ i ] % a [ j ] == 0 ) { dp [ i ] = Math . max ( dp [ i ] , 1 + dp [ j ] ) ; } } res = Math . max ( res , dp [ i ] ) ; } return ( res == 1 ) ? - 1 : res ; } public static void main ( String [ ] args ) { int a [ ] = { 2 , 4 , 6 , 1 , 3 , 11 } ; int n = a . length ; System . out . println ( find ( n , a ) ) ; } }