Predict the Winner

Dynamic Programming
Medium

Approach

Diagrams

Analysis

Time

Space

class Solution:
    def PredictTheWinner(self, points):
        totalPoints = sum(points)

        playerOneScore = self.getMaxPoints(points, totalPoints)
        playerTwoScore = totalPoints - playerOneScore

        return playerOneScore >= playerTwoScore

    def getMaxPoints(self, points, totalPoints):
        if len(points) <= 2:
            return max(points)

        # Get max points for other player if this player chooses first element
        ifThisPlayerChoosesFirst = self.getMaxPoints(points[1:], totalPoints - points[0])

        # Get max points for other player if this player chooses last element
        ifThisPlayerChoosesLast = self.getMaxPoints(points[:-1], totalPoints - points[-1])

        # Minimize points for other player
        minPointsForOtherPlayer = min(ifThisPlayerChoosesFirst, ifThisPlayerChoosesLast)

        # Maximize points for this player
        maxPointsForThisPlayer = totalPoints - minPointsForOtherPlayer

        return maxPointsForThisPlayer

Learn

#Dynamic Programming

#Minimax

Videos