Optimal Strategy for a Game | Set 2 | Java program to find out maximum value from a given sequence of coins ; For both of your choices , the opponent gives you total sum minus maximum of his value ; Returns optimal value possible that a player can collect from an array of coins of size n . Note than n must be even ; Driver code
import java . io . * ; class GFG { static int oSRec ( int [ ] arr , int i , int j , int sum ) { if ( j == i + 1 ) return Math . max ( arr [ i ] , arr [ j ] ) ; return Math . max ( ( sum - oSRec ( arr , i + 1 , j , sum - arr [ i ] ) ) , ( sum - oSRec ( arr , i , j - 1 , sum - arr [ j ] ) ) ) ; } static int optimalStrategyOfGame ( int [ ] arr , int n ) { int sum = 0 ; for ( int i = 0 ; i < n ; i ++ ) { sum += arr [ i ] ; } return oSRec ( arr , 0 , n - 1 , sum ) ; } static public void main ( String [ ] args ) { int [ ] arr1 = { 8 , 15 , 3 , 7 } ; int n = arr1 . length ; System . out . println ( optimalStrategyOfGame ( arr1 , n ) ) ; int [ ] arr2 = { 2 , 2 , 2 , 2 } ; n = arr2 . length ; System . out . println ( optimalStrategyOfGame ( arr2 , n ) ) ; int [ ] arr3 = { 20 , 30 , 2 , 2 , 2 , 10 } ; n = arr3 . length ; System . out . println ( optimalStrategyOfGame ( arr3 , n ) ) ; } }