Longest dividing subsequence | Dynamic Programming C ++ implementation of lds problem ; lds ( ) returns the length of the longest dividing subsequence in arr [ ] of size n ; Compute optimized lds values in bottom up manner ; Return maximum value in lds [ ] ; Driver program to test above function
#include <bits/stdc++.h> NEW_LINE using namespace std ; int lds ( int arr [ ] , int n ) { int lds [ n ] ; lds [ 0 ] = 1 ; for ( int i = 1 ; i < n ; i ++ ) { lds [ i ] = 1 ; for ( int j = 0 ; j < i ; j ++ ) if ( lds [ j ] != 0 && arr [ i ] % arr [ j ] == 0 ) lds [ i ] = max ( lds [ i ] , lds [ j ] + 1 ) ; } return * max_element ( lds , lds + n ) ; } int main ( ) { int arr [ ] = { 2 , 11 , 16 , 12 , 36 , 60 , 71 , 17 , 29 , 144 , 288 , 129 , 432 , 993 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; printf ( " Length ▁ of ▁ lds ▁ is ▁ % d STRNEWLINE " , lds ( arr , n ) ) ; return 0 ; }