Q45 Optimal Strategy For A Game | Practice | GeeksforGeeks | leetcode 46

//{ Driver Code Starts
import java.util.*;
import java.io.*;
import java.lang.*;

class OptimalStrategy
{
    public static void main (String[] args) {
        
        //taking input using Scanner class
        Scanner sc = new Scanner(System.in);
        
        //taking total number of testcases
        int t = sc.nextInt();
        
        while(t-- > 0)
        {
            //taking number of elements
            int n = sc.nextInt();
            int arr[] = new int[n];
            
            //inserting the elements
            for(int i = 0; i < n; i++)
                arr[i] = sc.nextInt();
                
           //calling the countMaximum() method of class solve
           System.out.println(new solve().countMaximum(arr, n)); 
        }
    }
    
    
}
// } Driver Code Ends



class solve
{
    //Function to find the maximum possible amount of money we can win.
    static long countMaximum(int arr[], int n)
    {
        //dp playlist ques - 45 , use of gap strategy
        
        //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);
                }
            }
        }
        
        return dp[0][n-1];
        //returning answer
    }
}
  
  
  
  
  
  
  
  
  
  
  //{ Driver Code Starts
import java.util.*;
import java.io.*;
import java.lang.*;

class OptimalStrategy
{
    public static void main (String[] args) {
        
        //taking input using Scanner class
        Scanner sc = new Scanner(System.in);
        
        //taking total number of testcases
        int t = sc.nextInt();
        
        while(t-- > 0)
        {
            //taking number of elements
            int n = sc.nextInt();
            int arr[] = new int[n];
            
            //inserting the elements
            for(int i = 0; i < n; i++)
                arr[i] = sc.nextInt();
                
           //calling the countMaximum() method of class solve
           System.out.println(new solve().countMaximum(arr, n)); 
        }
    }
    
    
}
// } Driver Code Ends



class solve
{
    //Function to find the maximum possible amount of money we can win.
    static long countMaximum(int arr[], int n)
    {
        //dp playlist ques - 45 , use of gap strategy
        
        //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);
                }
            }
        }
        
        return dp[0][n-1];
        //returning answer
    }
}