Maximize sum of odd | 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
def recursiveChoosing ( arr , start , M , dp ) : NEW_LINE INDENT key = ( start , M ) NEW_LINE if start >= N : NEW_LINE INDENT return 0 NEW_LINE DEDENT if N - start <= 2 * M : NEW_LINE INDENT return sum ( arr [ start : ] ) NEW_LINE DEDENT psa = 0 NEW_LINE total = sum ( arr [ start : ] ) NEW_LINE if key in dp : NEW_LINE INDENT return dp [ key ] NEW_LINE DEDENT for x in range ( 1 , 2 * M + 1 ) : NEW_LINE INDENT psb = recursiveChoosing ( arr , start + x , max ( x , M ) , dp ) NEW_LINE psa = max ( psa , total - psb ) NEW_LINE DEDENT dp [ key ] = psa NEW_LINE return dp [ key ] NEW_LINE DEDENT arr = [ 2 , 7 , 9 , 4 , 4 ] NEW_LINE N = len ( arr ) NEW_LINE dp = { } NEW_LINE print ( recursiveChoosing ( arr , 0 , 1 , dp ) ) NEW_LINE