Length of longest increasing index dividing subsequence | C ++ program to find the length of the longest increasing sub - sequence such that the index of the element is divisible by index of previous element ; Function to find the length of the longest increasing sub - sequence such that the index of the element is divisible by index of previous element ; Initialize the dp [ ] array with 1 as a single element will be of 1 length ; Traverse the given array ; If the index is divisible by the previous index ; if increasing subsequence identified ; Longest length is stored ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int LIIDS ( int arr [ ] , int N ) { int dp [ N + 1 ] ; int ans = 0 ; for ( int i = 1 ; i <= N ; i ++ ) { dp [ i ] = 1 ; } for ( int i = 1 ; i <= N ; i ++ ) { for ( int j = i + i ; j <= N ; j += i ) { if ( arr [ j ] > arr [ i ] ) { dp [ j ] = max ( dp [ j ] , dp [ i ] + 1 ) ; } } ans = max ( ans , dp [ i ] ) ; } return ans ; } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 7 , 9 , 10 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << LIIDS ( arr , N ) ; return 0 ; }