Longest increasing subsequence consisting of elements from indices divisible by previously selected indices | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findMaxLength ( int N , vector < int > arr ) { vector < int > dp ( N + 1 , 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 ] = max ( dp [ j ] , dp [ i ] + 1 ) ; } } } return * max_element ( dp . begin ( ) , dp . end ( ) ) ; } int main ( ) { vector < int > arr { 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 } ; int N = arr . size ( ) ; cout << findMaxLength ( N , arr ) ; return 0 ; }