Subsequence X of length K such that gcd ( X [ 0 ] , X [ 1 ] ) + ( X [ 2 ] , X [ 3 ] ) + ... is maximized | Python3 program to find the sum of the addition of all possible subsets ; Recursive function to find the maximum value of the given recurrence ; If we get K elements ; If we have reached the end and K elements are not there ; If the state has been visited ; Iterate for every element as the next possible element and take the element which gives the maximum answer ; If this element is the first element in the individual pair in the subsequence then simply recurrence with the last element as i - th index ; If this element is the second element in the individual pair , the find gcd with the previous element and add to the answer and recur for the next element ; Driver Code
from math import gcd as __gcd NEW_LINE MAX = 100 NEW_LINE def recur ( ind , cnt , last , a , n , k , dp ) : NEW_LINE INDENT if ( cnt == k ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( ind == n ) : NEW_LINE INDENT return - 10 ** 9 NEW_LINE DEDENT if ( dp [ ind ] [ cnt ] != - 1 ) : NEW_LINE INDENT return dp [ ind ] [ cnt ] NEW_LINE DEDENT ans = 0 NEW_LINE for i in range ( ind , n ) : NEW_LINE INDENT if ( cnt % 2 == 0 ) : NEW_LINE INDENT ans = max ( ans , recur ( i + 1 , cnt + 1 , i , a , n , k , dp ) ) NEW_LINE DEDENT else : NEW_LINE INDENT ans = max ( ans , __gcd ( a [ last ] , a [ i ] ) + recur ( i + 1 , cnt + 1 , 0 , a , n , k , dp ) ) NEW_LINE DEDENT DEDENT dp [ ind ] [ cnt ] = ans NEW_LINE return ans NEW_LINE DEDENT a = [ 4 , 5 , 3 , 7 , 8 , 10 , 9 , 8 ] NEW_LINE n = len ( a ) NEW_LINE k = 4 ; NEW_LINE dp = [ [ - 1 for i in range ( MAX ) ] for i in range ( n ) ] NEW_LINE print ( recur ( 0 , 0 , 0 , a , n , k , dp ) ) NEW_LINE