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
using System ; using System . Linq ; public class GFG { static int lds ( int [ ] arr , int n ) { int [ ] lds = new int [ 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 ] = Math . Max ( lds [ i ] , lds [ j ] + 1 ) ; } int max = lds . Max ( ) ; return max ; } public static void Main ( ) { int [ ] arr = { 2 , 11 , 16 , 12 , 36 , 60 , 71 , 17 , 29 , 144 , 288 , 129 , 432 , 993 } ; int n = arr . Length ; Console . Write ( " Length ▁ of ▁ lds ▁ is ▁ " + lds ( arr , n ) ) ; } }