class Solution {
    public boolean PredictTheWinner(int[] arr) {
        //dp playlist ques - 45 , use of gap strategy
        
        //finding total
        int n = arr.length , total = 0;

        for(int i = 0 ; i < n ; i++)
        total += arr[i];

        //making the dp
        int [][]dp = new int[n][n];
        
        //traversing & handling trivial cases and rest of the dp
        for(int gap = 0 ; gap <  n ; gap++){
            
            for(int i = 0 , j = gap ; j < n ; i++ , j++){
                
                //when only one coin
                if(gap == 0)
                dp[i][j] = arr[i];  //i==j
                
                //when only 2 coin, you take maximum of 2
                else if(gap == 1)
                dp[i][j] = Math.max(arr[i],arr[j]);
                
                //when more than 2 coins
                else{
                    /* if you chose ith coin , the opponent will choose the
                    next coin such that you get minimum of next choice
                    */
                    int cost1 = arr[i] + Math.min(dp[i+2][j],dp[i+1][j-1]);
                    
                    /* if you chose ith coin , the opponent will choose the
                    next coin such that you get minimum of next choice
                    */
                    int cost2 = arr[j] + Math.min(dp[i+1][j-1] , dp[i][j-2]);
                    
                    //but you will make choices such that you get max of cost1
                    //and cost2
                    dp[i][j] = Math.max(cost1 , cost2);
                }
            }
        }
        //now your final maximum score is in dp[0][n-1] , opponent score will be
        int opponent = total - dp[0][n-1];
        
        //if opponent score is greater than yours return false else true
        return opponent > dp[0][n-1] ? false : true;
    }
}