Maximum possible sum of non | C ++ program for the above approach ; Function to find the maximum sum not exceeding K possible by selecting a subset of non - adjacent elements ; Base Case ; Not selecting current element ; If selecting current element is possible ; Return answer ; Driver Code ; Given array arr [ ] ; Given K ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxSum ( int a [ ] , int n , int k ) { if ( n <= 0 ) return 0 ; int option = maxSum ( a , n - 1 , k ) ; if ( k >= a [ n - 1 ] ) option = max ( option , a [ n - 1 ] + maxSum ( a , n - 2 , k - a [ n - 1 ] ) ) ; return option ; } int main ( ) { int arr [ ] = { 50 , 10 , 20 , 30 , 40 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; int K = 100 ; cout << ( maxSum ( arr , N , K ) ) ; }