Maximum sum such that no two elements are adjacent | Set 2 | C ++ program to implement above approach ; variable to store states of dp ; variable to check if a given state has been solved ; Function to find the maximum sum subsequence such that no two elements are adjacent ; Base case ; To check if a state has been solved ; Required recurrence relation ; Returning the value ; Driver code
#include <bits/stdc++.h> NEW_LINE #define maxLen  10 NEW_LINE using namespace std ; int dp [ maxLen ] ; bool v [ maxLen ] ; int maxSum ( int arr [ ] , int i , int n ) { if ( i >= n ) return 0 ; if ( v [ i ] ) return dp [ i ] ; v [ i ] = 1 ; dp [ i ] = max ( maxSum ( arr , i + 1 , n ) , arr [ i ] + maxSum ( arr , i + 2 , n ) ) ; return dp [ i ] ; } int main ( ) { int arr [ ] = { 12 , 9 , 7 , 33 } ; int n = sizeof ( arr ) / sizeof ( int ) ; cout << maxSum ( arr , 0 , n ) ; return 0 ; }