Find the winner of a game of removing at most 3 stones from a pile in each turn | Java program for the above approach ; Function to find the maximum score of Player 1 ; Base Case ; If the result is already computed , then return the result ; Variable to store maximum score ; Pick one stone ; Pick 2 stones ; Pick 3 stones ; Return the score of the player ; Function to find the winner of the game ; Create a 1D table , dp of size N ; Store the result ; Player 1 wins ; PLayer 2 wins ; Tie ; Driver Code ; Given Input ; Function Call
import java . util . * ; class GFG { static int ans = 0 ; static int maximumStonesUtil ( int [ ] arr , int n , int i , int [ ] dp ) { if ( i >= n ) return 0 ; ans = dp [ i ] ; if ( ans != - 1 ) return ans ; ans = Integer . MIN_VALUE ; ans = Math . max ( ans , arr [ i ] - maximumStonesUtil ( arr , n , i + 1 , dp ) ) ; if ( i + 1 < n ) ans = Math . max ( ans , arr [ i ] + arr [ i + 1 ] - maximumStonesUtil ( arr , n , i + 2 , dp ) ) ; if ( i + 2 < n ) ans = Math . max ( ans , arr [ i ] + arr [ i + 1 ] + arr [ i + 2 ] - maximumStonesUtil ( arr , n , i + 3 , dp ) ) ; return ans ; } static String maximumStones ( int [ ] arr , int n ) { int [ ] dp = new int [ n ] ; Arrays . fill ( dp , - 1 ) ; int res = maximumStonesUtil ( arr , n , 0 , dp ) ; if ( res > 0 ) return " Player1" ; else if ( res < 0 ) return " Player2" ; else return " Tie " ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 2 , 3 , 7 } ; int n = arr . length ; System . out . print ( maximumStones ( arr , n ) ) ; } }