Longest increasing subsequence consisting of elements from indices divisible by previously selected indices | Java program for the above approach ; Function to find length of longest subsequence generated that satisfies the specified conditions ; Stores the length of longest subsequences of all lengths ; Iterate through the given array ; Iterate through the multiples i ; Update dp [ j ] as maximum of dp [ j ] and dp [ i ] + 1 ; Return the maximum element in dp [ ] as the length of longest subsequence ; Driver Code ; Function Call
import java . util . * ; class GFG { static int findMaxLength ( int N , int [ ] arr ) { int [ ] dp = new int [ N + 1 ] ; Arrays . fill ( dp , 1 ) ; for ( int i = 1 ; i <= N ; i ++ ) { for ( int j = 2 * i ; j <= N ; j += i ) { if ( arr [ i - 1 ] < arr [ j - 1 ] ) { dp [ j ] = Math . max ( dp [ j ] , dp [ i ] + 1 ) ; } } } return Arrays . stream ( dp ) . max ( ) . getAsInt ( ) ; } public static void main ( String [ ] args ) { int [ ] arr = { 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 } ; int N = arr . length ; System . out . print ( findMaxLength ( N , arr ) ) ; } }