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 Math . 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 ; Intitialising the dp table ; Base case ; Condition to select the current element ; Condition to not select the current element if possible ; Driver code
using System ; class GFG { static int MaximumSum ( int [ ] a , int n ) { int [ , ] dp = new int [ n + 1 , n + 1 ] ; for ( int i = 0 ; i < n + 1 ; i ++ ) { for ( int j = 0 ; j < n + 1 ; j ++ ) dp [ i , j ] = Int32 . MinValue ; } for ( int i = 0 ; i < n + 1 ; i ++ ) dp [ i , 0 ] = 0 ; for ( int i = 1 ; i <= n ; i ++ ) { for ( int j = 1 ; j <= i ; j ++ ) { int val = Int32 . MinValue ; if ( ( i - 2 >= 0 && dp [ i - 2 , j - 1 ] != Int32 . MinValue ) 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 ] ; } public static void Main ( ) { int [ ] A = { 1 , 2 , 3 , 4 , 5 , 6 } ; int N = A . Length ; Console . Write ( MaximumSum ( A , N ) ) ; } }