Problem Statement

You are given an array A of size N. The array contains integers and is of even length. The elements of the array represent N coin of values V1, V2, ....Vn. You play against an opponent in an alternating way.

In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin.

You need to determine the maximum possible amount of money you can win if you go first.Note: Both the players are playing optimally.

Example 1:

Input:
N = 4
A[] = {5,3,7,10}
Output:15
Explanation:The user collects maximum
value as 15(10 + 5)

Example 2:

Input:
N = 4
A[] = {8,15,3,7}
Output:22
Explanation:The user collects maximum
value as 22(7 + 15)

Approach

The following intuition helps us to solve the problem

1. Assume worst when things happen to you
2. Do best when you can

Reference Video

https://www.youtube.com/watch?v=ww4V7vRIzSk&ab_channel=Pepcoding

Code

long long maximumAmount(int arr[], int n) 
{
    int dp[n][n];
    
    for(int gap=0;gap<n;gap++)
    {
        for(int i=0,j=gap;j<n;i++,j++)
        {
            if(gap==0)
            dp[i][j] = arr[i];
            
            else if(gap==1)
            dp[i][j] = max(arr[i],arr[j]);
            
            else
            dp[i][j] = max(arr[i]+min(dp[i+2][j],dp[i+1][j-1]),arr[j]+min(dp[i+1][j-1],dp[i][j-2]));
        }
    }
    return dp[0][n-1];
}