Print all Longest dividing subsequence in an Array | C ++ program for the above approach ; Function to print LDS [ i ] element ; Traverse the Max [ ] ; Function to construct and print Longest Dividing Subsequence ; 2D vector for storing sequences ; Push the first element to LDS [ ] [ ] ; Iterate over all element ; Loop for every index till i ; if current elements divides arr [ i ] and length is greater than the previous index , then insert the current element to the sequences LDS [ i ] ; L [ i ] ends with arr [ i ] ; LDS stores the sequences till each element of arr [ ] Traverse the LDS [ ] [ ] to find the the maximum length ; Print all LDS with maximum length ; Find size ; If size = maxLength ; Print LDS ; Driver Code ; Function Call
#include " bits / stdc + + . h " NEW_LINE using namespace std ; void printLDS ( vector < int > & Max ) { for ( auto & it : Max ) { cout << it << ' ▁ ' ; } } void LongestDividingSeq ( int arr [ ] , int N ) { vector < vector < int > > LDS ( N ) ; LDS [ 0 ] . push_back ( arr [ 0 ] ) ; for ( int i = 1 ; i < N ; i ++ ) { for ( int j = 0 ; j < i ; j ++ ) { if ( ( arr [ i ] % arr [ j ] == 0 ) && ( LDS [ i ] . size ( ) < LDS [ j ] . size ( ) + 1 ) ) LDS [ i ] = LDS [ j ] ; } LDS [ i ] . push_back ( arr [ i ] ) ; } int maxLength = 0 ; for ( int i = 0 ; i < N ; i ++ ) { int x = LDS [ i ] . size ( ) ; maxLength = max ( maxLength , x ) ; } for ( int i = 0 ; i < N ; i ++ ) { int size = LDS [ i ] . size ( ) ; if ( size == maxLength ) { printLDS ( LDS [ i ] ) ; cout << ' ' ; } } } int main ( ) { int arr [ ] = { 2 , 11 , 16 , 12 , 36 , 60 , 71 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; LongestDividingSeq ( arr , N ) ; return 0 ; }