02 Optimal Strategy for a Game

Optimal Strategy For A Game | Practice | GeeksforGeeks

GeeksForGeeks Question

TLE Solution discussed in class

long long optimalStrategy(int arr[], int i, int j) {
    //BASE CASE
    if(i > j)
        return 0;
    
    long long choice1 = arr[i] + min(optimalStrategy(arr, i + 2, j), optimalStrategy(arr, i + 1, j - 1));
    long long choice2 = arr[j] + min(optimalStrategy(arr, i + 1, j - 1), optimalStrategy(arr, i, j - 2));
    
    long long ans = max(choice1, choice2);
    return ans;
}
long long maximumAmount(int arr[], int n){
    return optimalStrategy(arr, 0, n - 1); 
}