Maximum sum of non | 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 ; Variable to store prefix sum for sub - array { i , j } ; Required recurrence relation ; Returning the value ; Driver code ; Input array
#include <bits/stdc++.h> NEW_LINE #define maxLen  10 NEW_LINE using namespace std ; int dp [ maxLen ] ; bool visit [ maxLen ] ; int maxSum ( int arr [ ] , int i , int n , int k ) { if ( i >= n ) return 0 ; if ( visit [ i ] ) return dp [ i ] ; visit [ i ] = 1 ; int tot = 0 ; dp [ i ] = maxSum ( arr , i + 1 , n , k ) ; for ( int j = i ; j < i + k and j < n ; j ++ ) { tot += arr [ j ] ; dp [ i ] = max ( dp [ i ] , tot + maxSum ( arr , j + 2 , n , k ) ) ; } return dp [ i ] ; } int main ( ) { int arr [ ] = { -1 , 2 , -3 , 4 , 5 } ; int k = 2 ; int n = sizeof ( arr ) / sizeof ( int ) ; cout << maxSum ( arr , 0 , n , k ) ; return 0 ; }