Optimal Strategy For A Game

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.

• Time : O(n * n)
• Space : O(n * n)

We can choose only one arr[l], arr[r] at once, and our goal is make largest sum.
In this case, we choose the way to get maximum difference if we pick arr[l] or arr[r].
So, the result helper returns maximum difference of we choose first.

We named as first pick sum as A ans second pick sum as B and helper returns max(A - B). Also we know A + B is sum(arr).

With Two formula we can calculate A with simple math.

• A + B = sum(arr)
• A - B = helper(arr)

Two formula can be convert to 2 * A = sum(arr) + helper(arr).

So we just return (sum(arr) + helper(arr)) / 2.

class Solution{
    long long dp[1000][1000];
    long long helper(int arr[], int l, int r) {
        if(l > r) return 0;
        if(dp[l][r] != -1) return dp[l][r];
        long long &res = dp[l][r] = LLONG_MIN;
        res = max(res, arr[l] - helper(arr, l + 1, r));
        res = max(res, arr[r] - helper(arr, l, r - 1));
        
        return res;
    }
public:
    long long maximumAmount(int arr[], int n){
        memset(dp, -1, sizeof dp);
        return (accumulate(arr, arr + n, 0ll) + helper(arr, 0, n - 1)) / 2;
    }
};