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 ; Base case ; When i is odd ; When i is even ; Maximum of if we pick last element or not ; Driver code
using System ; class GFG { static int MaximumSum ( int [ ] a , int n ) { int [ , ] dp = new int [ n + 1 , 2 ] ; dp [ 2 , 1 ] = a [ 1 ] ; dp [ 2 , 0 ] = a [ 0 ] ; for ( int i = 3 ; i < n + 1 ; i ++ ) { if ( i % 2 == 1 ) { int temp = Math . Max ( ( Math . Max ( dp [ i - 3 , 1 ] , dp [ i - 3 , 0 ] ) ) , Math . Max ( dp [ i - 2 , 1 ] , dp [ i - 2 , 0 ] ) ) ; dp [ i , 1 ] = a [ i - 1 ] + temp ; dp [ i , 0 ] = Math . Max ( ( Math . Max ( a [ i - 2 ] + dp [ i - 2 , 0 ] , a [ i - 2 ] + dp [ i - 3 , 1 ] ) ) , Math . Max ( a [ i - 2 ] + dp [ i - 3 , 0 ] , a [ i - 3 ] + dp [ i - 3 , 0 ] ) ) ; } else { dp [ i , 1 ] = a [ i - 1 ] + ( Math . Max ( ( Math . Max ( dp [ i - 2 , 1 ] , dp [ i - 2 , 0 ] ) ) , dp [ i - 1 , 0 ] ) ) ; dp [ i , 0 ] = a [ i - 2 ] + dp [ i - 2 , 0 ] ; } } return Math . Max ( dp [ n , 1 ] , dp [ n , 0 ] ) ; } static int max ( int [ ] arr ) { return 1 ; } public static void Main ( String [ ] args ) { int [ ] A = { 1 , 2 , 3 , 4 , 5 , 6 } ; int N = A . Length ; Console . Write ( MaximumSum ( A , N ) ) ; } }