Subsequence X of length K such that gcd ( X [ 0 ] , X [ 1 ] ) + ( X [ 2 ] , X [ 3 ] ) + ... is maximized | Java 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
import java . util . * ; class GFG { static int MAX = 100 ; static int recur ( int ind , int cnt , int last , int a [ ] , int n , int k , int dp [ ] [ ] ) { if ( cnt == k ) return 0 ; if ( ind == n ) return ( int ) - 1e9 ; if ( dp [ ind ] [ cnt ] != - 1 ) return dp [ ind ] [ cnt ] ; int ans = 0 ; for ( int 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 ; } static int __gcd ( int a , int b ) { if ( b == 0 ) return a ; return __gcd ( b , a % b ) ; } public static void main ( String [ ] args ) { int a [ ] = { 4 , 5 , 3 , 7 , 8 , 10 , 9 , 8 } ; int n = a . length ; int k = 4 ; int [ ] [ ] dp = new int [ n ] [ MAX ] ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < MAX ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } System . out . println ( recur ( 0 , 0 , 0 , a , n , k , dp ) ) ; } }