Longest subsequence having maximum GCD between any pair of distinct elements | Python3 program for the above approach ; Function to find GCD of pair with maximum GCD ; Stores maximum element of arr [ ] ; Find the maximum element ; Maintain a count array ; Store the frequency of arr [ ] ; Stores the multiples of a number ; Iterate over the range [ MAX , 1 ] ; Iterate from current potential GCD till it is less than MAX ; A multiple found ; Increment potential GCD by itself io check i , 2 i , 3 i ... ; If 2 multiples found max GCD found ; Function to find longest subsequence such that GCD of any two distinct integers is maximum ; Base Cases ; Compare current GCD to the maximum GCD ; If true increment and move the pointer ; Return max of either subsequences ; Drivers Code ; Sorted array ; Function call to calculate GCD of pair with maximum GCD ; Print the result
import math NEW_LINE def findMaxGCD ( arr , N ) : NEW_LINE INDENT high = 0 NEW_LINE for i in range ( 0 , N ) : NEW_LINE INDENT high = max ( high , arr [ i ] ) NEW_LINE DEDENT count = [ 0 ] * ( high + 1 ) NEW_LINE for i in range ( 0 , N ) : NEW_LINE INDENT count [ arr [ i ] ] += 1 NEW_LINE DEDENT counter = 0 NEW_LINE for i in range ( high , 0 , - 1 ) : NEW_LINE INDENT j = i NEW_LINE while ( j <= high ) : NEW_LINE INDENT if ( count [ j ] > 0 ) : NEW_LINE INDENT counter += count [ j ] NEW_LINE DEDENT j += i NEW_LINE if ( counter == 2 ) : NEW_LINE INDENT return i NEW_LINE DEDENT DEDENT counter = 0 NEW_LINE DEDENT DEDENT def maxlen ( i , j ) : NEW_LINE INDENT a = 0 NEW_LINE if i >= N or j >= N : NEW_LINE INDENT return 0 NEW_LINE DEDENT if math . gcd ( arr [ i ] , arr1 [ j ] ) == maxgcd and arr [ i ] != arr1 [ j ] : NEW_LINE INDENT a = max ( a , 1 + maxlen ( i , j + 1 ) ) NEW_LINE return a NEW_LINE DEDENT return max ( maxlen ( i + 1 , j ) , maxlen ( i , j + 1 ) ) NEW_LINE DEDENT arr = [ 1 , 2 , 8 , 5 , 6 ] NEW_LINE N = len ( arr ) NEW_LINE arr1 = sorted ( arr ) NEW_LINE maxgcd = findMaxGCD ( arr , N ) NEW_LINE print ( maxlen ( 0 , 0 ) ) NEW_LINE