Maximize sum of odd | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int recursiveChoosing ( int arr [ ] , int start , int M , map < pair < int , int > , int > dp , int N ) { pair < int , int > key ( start , M ) ; if ( start >= N ) { return 0 ; } if ( N - start <= 2 * M ) { int Sum = 0 ; for ( int i = start ; i < N ; i ++ ) { Sum = Sum + arr [ i ] ; } return Sum ; } int sum = 0 ; for ( int i = start ; i < N ; i ++ ) { sum = sum + arr [ i ] ; } int total = sum ; if ( dp . find ( key ) != dp . end ( ) ) { return dp [ key ] ; } int psa = 0 ; for ( int x = 1 ; x < 2 * M + 1 ; x ++ ) { int psb = recursiveChoosing ( arr , start + x , max ( x , M ) , dp , N ) ; psa = max ( psa , total - psb ) ; } dp [ key ] = psa ; return dp [ key ] ; } int main ( ) { int arr [ ] = { 2 , 7 , 9 , 4 , 4 } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; map < pair < int , int > , int > dp ; cout << recursiveChoosing ( arr , 0 , 1 , dp , N ) ; return 0 ; }