Optimal Strategy for a Game | Set 3 | C ++ implementation ; Calculates the maximum score possible for P1 If only the bags from beg to ed were available ; Length of the game ; Which turn is being played ; Base case i . e last turn ; if it is P1 's turn ; if P2 's turn ; Player picks money from the left end ; Player picks money from the right end ; if it is player 1 's turn then  current picked score added to  his total. choose maximum of  the two scores as P1 tries to  maximize his score. ; if player 2 ' s ▁ turn ▁ don ' t add current picked bag score to total . choose minimum of the two scores as P2 tries to minimize P1 's score. ; Driver Code ; Input array ; Function Calling
#include <bits/stdc++.h> NEW_LINE using namespace std ; pair < int , string > maxScore ( vector < int > money , int beg , int ed ) { int totalTurns = money . size ( ) ; int turnsTillNow = beg + ( ( totalTurns - 1 ) - ed ) ; if ( beg == ed ) { if ( turnsTillNow % 2 == 0 ) return { money [ beg ] , " L " } ; else return { 0 , " L " } ; } pair < int , string > scoreOne = maxScore ( money , beg + 1 , ed ) ; pair < int , string > scoreTwo = maxScore ( money , beg , ed - 1 ) ; if ( turnsTillNow % 2 == 0 ) { if ( money [ beg ] + scoreOne . first > money [ ed ] + scoreTwo . first ) { return { money [ beg ] + scoreOne . first , " L " + scoreOne . second } ; } else return { money [ ed ] + scoreTwo . first , " R " + scoreTwo . second } ; } else { if ( scoreOne . first < scoreTwo . first ) return { scoreOne . first , " L " + scoreOne . second } ; else return { scoreTwo . first , " R " + scoreTwo . second } ; } } int main ( ) { int ar [ ] = { 10 , 80 , 90 , 30 } ; int arraySize = sizeof ( ar ) / sizeof ( int ) ; vector < int > bags ( ar , ar + arraySize ) ; pair < int , string > ans = maxScore ( bags , 0 , bags . size ( ) - 1 ) ; cout << ans . first << " ▁ " << ans . second << endl ; return 0 ; }