Size of the largest divisible subset in an Array | C ++ implementation of the above approach ; Function to find the size of the largest divisible subarray ; Mark all elements of the array ; Traverse reverse ; For all multiples of i ; Return the required answer ; Driver code ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  1000005 NEW_LINE int maximum_set ( int a [ ] , int n ) { int dp [ N ] = { 0 } ; for ( int i = 0 ; i < n ; i ++ ) dp [ a [ i ] ] = 1 ; int ans = 1 ; for ( int i = N - 1 ; i >= 1 ; i -- ) { if ( dp [ i ] != 0 ) { for ( int j = 2 * i ; j < N ; j += i ) { dp [ i ] = max ( dp [ i ] , 1 + dp [ j ] ) ; ans = max ( ans , dp [ i ] ) ; } } } return ans ; } int main ( ) { int arr [ ] = { 3 , 4 , 6 , 8 , 10 , 18 , 21 , 24 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << maximum_set ( arr , n ) ; return 0 ; }