Largest subsequence such that all indices and all values are multiples individually | C ++ program for the above approach ; Function that print maximum length of array ; dp [ ] array to store the maximum length ; Find all divisors of i ; If the current value is greater than the divisor 's value ; If current value is greater than the divisor 's value  and s is not equal  to current index ; Condition if current value is greater than the divisor 's value ; Computing the greatest value ; Printing maximum length of array ; Driver Code ; Given array arr [ ] ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; void maxLength ( int arr [ ] , int n ) { vector < int > dp ( n , 1 ) ; for ( int i = n - 1 ; i > 1 ; i -- ) { for ( int j = 1 ; j <= sqrt ( i ) ; j ++ ) { if ( i % j == 0 ) { int s = i / j ; if ( s == j ) { if ( arr [ i ] > arr [ s ] ) { dp [ s ] = max ( dp [ i ] + 1 , dp [ s ] ) ; } } else { if ( s != i && arr [ i ] > arr [ s ] ) dp [ s ] = max ( dp [ i ] + 1 , dp [ s ] ) ; if ( arr [ i ] > arr [ j ] ) { dp [ j ] = max ( dp [ i ] + 1 , dp [ j ] ) ; } } } } } int max = 0 ; for ( int i = 1 ; i < n ; i ++ ) { if ( dp [ i ] > max ) max = dp [ i ] ; } cout << max << " STRNEWLINE " ; } int main ( ) { int arr [ ] = { 0 , 1 , 4 , 2 , 3 , 6 , 4 , 9 } ; int size = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; maxLength ( arr , size ) ; return 0 ; }