Size of the largest divisible subset in an Array | Python3 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
N = 1000005 NEW_LINE def maximum_set ( a , n ) : NEW_LINE INDENT dp = [ 0 for i in range ( N ) ] NEW_LINE for i in a : NEW_LINE INDENT dp [ i ] = 1 NEW_LINE DEDENT ans = 1 NEW_LINE for i in range ( N - 1 , 0 , - 1 ) : NEW_LINE INDENT if ( dp [ i ] != 0 ) : NEW_LINE INDENT for j in range ( 2 * i , N , i ) : NEW_LINE INDENT dp [ i ] = max ( dp [ i ] , 1 + dp [ j ] ) NEW_LINE ans = max ( ans , dp [ i ] ) NEW_LINE DEDENT DEDENT DEDENT return ans NEW_LINE DEDENT arr = [ 3 , 4 , 6 , 8 , 10 , 18 , 21 , 24 ] NEW_LINE n = len ( arr ) NEW_LINE print ( maximum_set ( arr , n ) ) NEW_LINE