Maximum sum such that exactly half of the elements are selected and no two adjacent | Java 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
import java . util . * ; 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 ; System . out . print ( MaximumSum ( A , N ) ) ; } }