Maximum sum such that exactly half of the elements are selected and no two adjacent | Function return the maximum sum possible under given condition ; Intitialising the dp table ; Base case ; Condition to select the current element ; Condition to not select the current element if possible ; Driver code
function MaximumSum ( a , n ) { let dp = [ ] ; for ( let i = 0 ; i < n + 1 ; i ++ ) dp . push ( Array ( n + 1 ) ) ; for ( let i = 0 ; i < n + 1 ; i ++ ) { for ( let j = 0 ; j < n + 1 ; j ++ ) dp [ i ] [ j ] = - 10000 ; } for ( let i = 0 ; i < n + 1 ; i ++ ) dp [ i ] [ 0 ] = 0 ; for ( let i = 1 ; i <= n ; i ++ ) { for ( let j = 1 ; j <= i ; j ++ ) { let val = - 10000 ; if ( ( i - 2 >= 0 && dp [ i - 2 , j - 1 ] != - 10000 ) i - 2 < 0 ) { val = a [ i - 1 ] + ( i - 2 >= 0 ? dp [ i - 2 ] [ j - 1 ] : 0 ) ; } if ( i - 1 >= j ) { val = Math . max ( val , dp [ i - 1 ] [ j ] ) ; } dp [ i ] [ j ] = val ; } } return dp [ n ] [ n / 2 ] } let A = [ 1 , 2 , 3 , 4 , 5 , 6 ] ; let N = A . length ; document . write ( MaximumSum ( A , N ) ) ;