Subsequence X of length K such that gcd ( X [ 0 ] , X [ 1 ] ) + ( X [ 2 ] , X [ 3 ] ) + ... is maximized | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX = 100 ; int recur ( int ind , int cnt , int last , int a [ ] , int n , int k , int dp [ ] [ MAX ] ) { if ( cnt == k ) return 0 ; if ( ind == n ) return -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 = max ( ans , recur ( i + 1 , cnt + 1 , i , a , n , k , dp ) ) ; else ans = max ( ans , __gcd ( a [ last ] , a [ i ] ) + recur ( i + 1 , cnt + 1 , 0 , a , n , k , dp ) ) ; } return dp [ ind ] [ cnt ] = ans ; } int main ( ) { int a [ ] = { 4 , 5 , 3 , 7 , 8 , 10 , 9 , 8 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; int k = 4 ; int dp [ n ] [ MAX ] ; memset ( dp , -1 , sizeof dp ) ; cout << recur ( 0 , 0 , 0 , a , n , k , dp ) ; }