Subsequence X of length K such that gcd ( X [ 0 ] , X [ 1 ] ) + ( X [ 2 ] , X [ 3 ] ) + ... is maximized | Javascript 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
let MAX = 100 ; function recur ( ind , cnt , last , a , n , k , dp ) { if ( cnt == k ) return 0 ; if ( ind == n ) return - 1e9 ; if ( dp [ ind ] [ cnt ] != - 1 ) return dp [ ind ] [ cnt ] ; let ans = 0 ; for ( let i = ind ; i < n ; i ++ ) { if ( cnt % 2 == 0 ) ans = Math . max ( ans , recur ( i + 1 , cnt + 1 , i , a , n , k , dp ) ) ; else ans = Math . max ( ans , __gcd ( a [ last ] , a [ i ] ) + recur ( i + 1 , cnt + 1 , 0 , a , n , k , dp ) ) ; } return dp [ ind ] [ cnt ] = ans ; } function __gcd ( a , b ) { if ( b == 0 ) return a ; return __gcd ( b , a % b ) ; } let a = [ 4 , 5 , 3 , 7 , 8 , 10 , 9 , 8 ] ; let n = a . length ; let k = 4 ; let dp = new Array ( n ) ; for ( let i = 0 ; i < n ; i ++ ) { dp [ i ] = new Array ( MAX ) ; for ( let j = 0 ; j < MAX ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } document . write ( recur ( 0 , 0 , 0 , a , n , k , dp ) ) ;