Maximum sum such that exactly half of the elements are selected and no two adjacent | 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
function MaximumSum ( a , n ) { var dp = Array . from ( Array ( n + 1 ) , ( ) => Array ( 2 ) . fill ( 0 ) ) ; dp [ 2 ] [ 1 ] = a [ 1 ] ; dp [ 2 ] [ 0 ] = a [ 0 ] ; for ( var i = 3 ; i < n + 1 ; i ++ ) { if ( i & 1 ) { var temp = ( [ dp [ i - 3 ] [ 1 ] , dp [ i - 3 ] [ 0 ] , dp [ i - 2 ] [ 1 ] , dp [ i - 2 ] [ 0 ] ] . reduce ( ( a , b ) => Math . max ( a , b ) ) ) ; dp [ i ] [ 1 ] = a [ i - 1 ] + temp ; dp [ i ] [ 0 ] = ( [ 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 ] ] . reduce ( ( a , b ) => Math . max ( a , b ) ) ) ; } else { dp [ i ] [ 1 ] = a [ i - 1 ] + ( [ dp [ i - 2 ] [ 1 ] , dp [ i - 2 ] [ 0 ] , dp [ i - 1 ] [ 0 ] ] . reduce ( ( a , b ) => Math . max ( a , b ) ) ) ; dp [ i ] [ 0 ] = a [ i - 2 ] + dp [ i - 2 ] [ 0 ] ; } } return Math . max ( dp [ n ] [ 1 ] , dp [ n ] [ 0 ] ) ; } var A = [ 1 , 2 , 3 , 4 , 5 , 6 ] ; var N = A . length ; document . write ( MaximumSum ( A , N ) ) ;