Maximum sum in an array such that every element has exactly one adjacent element to it | C ++ implementation of the approach ; To store the states of dp ; Function to return the maximized sum ; Base case ; Checks if a state is already solved ; Recurrence relation ; Return the result ; Driver code
#include <bits/stdc++.h> NEW_LINE #define arrSize  51 NEW_LINE using namespace std ; int dp [ arrSize ] ; bool v [ arrSize ] ; int sumMax ( int i , int arr [ ] , int n ) { if ( i >= n - 1 ) return 0 ; if ( v [ i ] ) return dp [ i ] ; v [ i ] = true ; dp [ i ] = max ( arr [ i ] + arr [ i + 1 ] + sumMax ( i + 3 , arr , n ) , sumMax ( i + 1 , arr , n ) ) ; return dp [ i ] ; } int main ( ) { int arr [ ] = { 1 , 1 , 1 , 1 } ; int n = sizeof ( arr ) / sizeof ( int ) ; cout << sumMax ( 0 , arr , n ) ; return 0 ; }