Maximize sum of odd | Java program for the above approach ; Function to find the maximum sum of array elements chosen by Player A according to the given criteria ; Store the key ; Corner Case ; Check if all the elements can be taken or not ; If the difference is less than or equal to the available chances then pick all numbers ; Find the sum of array elements over the range [ start , N ] ; If yes then return that value ; Traverse over the range [ 1 , 2 * M ] ; Sum of elements for Player A ; Even chance sum can be obtained by subtracting the odd chances sum - total and picking up the maximum from that ; Storing the value in dictionary ; Return the maximum sum of odd chances ; Driver code ; Stores the precomputed values ; Function Call
import java . util . * ; import java . awt . Point ; public class GFG { static int recursiveChoosing ( int [ ] arr , int start , int M , HashMap < Point , Integer > dp ) { Point key = new Point ( start , M ) ; if ( start >= arr . length ) { return 0 ; } if ( arr . length - start <= 2 * M ) { int Sum = 0 ; for ( int i = start ; i < arr . length ; i ++ ) { Sum = Sum + arr [ i ] ; } return Sum ; } int sum = 0 ; for ( int i = start ; i < arr . length ; i ++ ) { sum = sum + arr [ i ] ; } int total = sum ; if ( dp . containsKey ( key ) ) { return dp . get ( key ) ; } int psa = 0 ; for ( int x = 1 ; x < 2 * M + 1 ; x ++ ) { int psb = recursiveChoosing ( arr , start + x , Math . max ( x , M ) , dp ) ; psa = Math . max ( psa , total - psb ) ; } dp . put ( key , psa ) ; return dp . get ( key ) ; } public static void main ( String [ ] args ) { int [ ] arr = { 2 , 7 , 9 , 4 , 4 } ; int N = arr . length ; HashMap < Point , Integer > dp = new HashMap < Point , Integer > ( ) ; System . out . print ( recursiveChoosing ( arr , 0 , 1 , dp ) ) ; } }