Find the winner of a game of removing at most 3 stones from a pile in each turn | 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 ; Given Input ; Function Call
def maximumStonesUtil ( arr , n , i , dp ) : NEW_LINE INDENT if ( i >= n ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT ans = dp [ i ] NEW_LINE if ( ans != - 1 ) : NEW_LINE INDENT return ans NEW_LINE DEDENT ans = - 2 ** 31 NEW_LINE ans = max ( ans , arr [ i ] - maximumStonesUtil ( arr , n , i + 1 , dp ) ) NEW_LINE if ( i + 1 < n ) : NEW_LINE INDENT ans = max ( ans , arr [ i ] + arr [ i + 1 ] - maximumStonesUtil ( arr , n , i + 2 , dp ) ) NEW_LINE DEDENT if ( i + 2 < n ) : NEW_LINE INDENT ans = max ( ans , arr [ i ] + arr [ i + 1 ] + arr [ i + 2 ] - maximumStonesUtil ( arr , n , i + 3 , dp ) ) NEW_LINE DEDENT return ans NEW_LINE DEDENT def maximumStones ( arr , n ) : NEW_LINE INDENT dp = [ - 1 ] * n NEW_LINE res = maximumStonesUtil ( arr , n , 0 , dp ) NEW_LINE if ( res > 0 ) : NEW_LINE INDENT return " Player1" NEW_LINE DEDENT elif ( res < 0 ) : NEW_LINE INDENT return " Player2" NEW_LINE DEDENT else : NEW_LINE INDENT return " Tie " NEW_LINE DEDENT DEDENT arr = [ 1 , 2 , 3 , 7 ] NEW_LINE n = len ( arr ) NEW_LINE print ( maximumStones ( arr , n ) ) NEW_LINE