Maximum sum such that exactly half of the elements are selected and no two adjacent | C ++ program to find maximum sum possible such that exactly floor ( N / 2 ) elements are selected and no two selected elements are adjacent to each other ; Function return the maximum sum possible under given condition ; Base case ; When i is odd ; When i is even ; Maximum of if we pick last element or not ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int MaximumSum ( int a [ ] , int n ) { int dp [ n + 1 ] [ 2 ] ; memset ( dp , 0 , sizeof ( dp ) ) ; dp [ 2 ] [ 1 ] = a [ 1 ] ; dp [ 2 ] [ 0 ] = a [ 0 ] ; for ( int i = 3 ; i < n + 1 ; i ++ ) { if ( i & 1 ) { int temp = max ( { dp [ i - 3 ] [ 1 ] , dp [ i - 3 ] [ 0 ] , dp [ i - 2 ] [ 1 ] , dp [ i - 2 ] [ 0 ] } ) ; dp [ i ] [ 1 ] = a [ i - 1 ] + temp ; dp [ i ] [ 0 ] = max ( { a [ i - 2 ] + dp [ i - 2 ] [ 0 ] , a [ i - 2 ] + dp [ i - 3 ] [ 1 ] , a [ i - 2 ] + dp [ i - 3 ] [ 0 ] , a [ i - 3 ] + dp [ i - 3 ] [ 0 ] } ) ; } else { dp [ i ] [ 1 ] = a [ i - 1 ] + max ( { dp [ i - 2 ] [ 1 ] , dp [ i - 2 ] [ 0 ] , dp [ i - 1 ] [ 0 ] } ) ; dp [ i ] [ 0 ] = a [ i - 2 ] + dp [ i - 2 ] [ 0 ] ; } } return max ( dp [ n ] [ 1 ] , dp [ n ] [ 0 ] ) ; } int main ( ) { int A [ ] = { 1 , 2 , 3 , 4 , 5 , 6 } ; int N = sizeof ( A ) / sizeof ( A [ 0 ] ) ; cout << MaximumSum ( A , N ) ; return 0 ; }