Optimal Strategy for a Game

Last Updated : 5 Dec, 2025

Given an array arr[] containing an even number of elements, where each element represents the value of a coin placed in a row. Two players(We and our friend) are playing the game, and in every turn a player can pick either the first coin or the last coin from the row. Once a coin is taken, it cannot be chosen again.
Determine the maximum amount of money we can surely secure if we move first, assuming the opponent is also playing greedily.

Examples:

Input: arr[] = [5, 3, 7, 10]
Output: 15
Explanation: We collects the maximum value as 15 (10 + 5). It is guaranteed that we cannot get more than 15 by any possible moves.

Input: arr[] = [8, 15, 3, 7]
Output: 22
Explanation: We collects the maximum value as 22 (7 + 15).

Try it on GfG Practice
redirect icon

Table of Content

Why greedy algorithm fail here?

Does choosing the best at each move give an optimal solution?
No. In the second example, this is how the game can be finished in two ways:

  • we chooses 8. 
    The opponent chooses 15. 
    we chooses 7. 
    The opponent chooses 3. 
    The total value collected by us : 15(8 + 7)
  • we chooses 7. 
    The opponent chooses 8. 
    we chooses 15. 
    The opponent chooses 3. 
    The total value collected by us : 22(7 + 15)

Note: If the user follows the second game state, the maximum value can be collected although the first move is not the best. 

[Naive Approach] Using Recursion – O(2^n) Time and O(n) Space

Suppose if we have values [vi, v(i+1), . . . ., vj], and we have choices to pick from either i or j index so at any turn, we have two choices:
Pick the ith coin (Vi):

  • Opponent chooses (i+1)th or jth coin to minimize our gain.
  • Maximum we can collect: Vi+ min(maxAmount(i+2,j), maxAmount(i+1,j−1))
    [i+2, j] if opponent picks (i+1)th, [i+1, j-1] if opponent picks jth.

Pick the jth coin (Vj):

  • Opponent chooses ith or (j-1)th coin optimally.
  • Maximum we can collect: Vj+min(maxAmount(i+1,j−1), maxAmount(i,j−2))
    [i+1, j-1] if opponent picks ith, [i, j-2] if opponent picks (j-1)th.

Finally, we pick the choice that gives the maximum total.

C++ 
//Driver Code Starts
#include <iostream>
#include<vector>
using namespace std;
//Driver Code Ends

int maxAmount(int i, int j, vector<int> &arr) {
    
   // Base case: If i > j, no more elements are left to pick
    if (i > j)
        return 0;

    // Option 1: Take the first element arr[i]
    int takeFirst = arr[i] + min(maxAmount(i + 2, j, arr), 
                                 maxAmount(i + 1, j - 1, arr));

    // Option 2: Take the last element arr[j]
    int takeLast = arr[j] + min(maxAmount(i + 1, j - 1, arr),
                                maxAmount(i, j - 2, arr));

    return max(takeFirst, takeLast);
}

int maximumAmount(vector<int> &arr) {
	
  	int n = arr.size();
    int res = maxAmount(0, n - 1, arr);

    return res;
}

//Driver Code Starts

int main() {

    vector<int> arr = {5, 3, 7, 10};
    int res = maximumAmount(arr);
    cout << res << endl;

    return 0;
}
//Driver Code Ends
Java 
//Driver Code Starts
import java.util.Arrays;

public class GFG {

//Driver Code Ends

    static int maxAmount(int i, int j, int[] arr) {
        // Base case: If i > j, no more elements are left to pick
        if (i > j)
            return 0;

        // Option 1: Take the first element arr[i]
        int takeFirst = arr[i] + Math.min(maxAmount(i + 2, j, arr), 
                                          maxAmount(i + 1, j - 1, arr));

        // Option 2: Take the last element arr[j]
        int takeLast = arr[j] + Math.min(maxAmount(i + 1, j - 1, arr),
                                         maxAmount(i, j - 2, arr));

        return Math.max(takeFirst, takeLast);
    }

    static int maximumAmount(int[] arr) {
        int n = arr.length;
        int res = maxAmount(0, n - 1, arr);
        return res;
    }

//Driver Code Starts

    public static void main(String[] args) {
        int[] arr = {5, 3, 7, 10};
        int res = maximumAmount(arr);
        System.out.println(res);
    }
}

//Driver Code Ends
Python 
def maxAmount(i, j, arr):
    # Base case: If i > j, no more elements are left to pick
    if i > j:
        return 0

    # Option 1: Take the first element arr[i]
    takeFirst = arr[i] + min(maxAmount(i + 2, j, arr),
                             maxAmount(i + 1, j - 1, arr))

    # Option 2: Take the last element arr[j]
    takeLast = arr[j] + min(maxAmount(i + 1, j - 1, arr),
                            maxAmount(i, j - 2, arr))

    return max(takeFirst, takeLast)

def maximumAmount(arr):
    n = len(arr)
    res = maxAmount(0, n - 1, arr)
    return res


#Driver Code Starts

if __name__ == "__main__":
    arr = [5, 3, 7, 10]
    res = maximumAmount(arr)
    print(res)

#Driver Code Ends
C# 
//Driver Code Starts
using System;

public class GFG{

//Driver Code Ends

    static int maxAmount(int i, int j, int[] arr) {
        // Base case: If i > j, no more elements are left to pick
        if (i > j)
            return 0;

        // Option 1: Take the first element arr[i]
        int takeFirst = arr[i] + Math.Min(maxAmount(i + 2, j, arr),
                                          maxAmount(i + 1, j - 1, arr));

        // Option 2: Take the last element arr[j]
        int takeLast = arr[j] + Math.Min(maxAmount(i + 1, j - 1, arr),
                                         maxAmount(i, j - 2, arr));

        return Math.Max(takeFirst, takeLast);
    }

    static int maximumAmount(int[] arr) {
        int n = arr.Length;
        int res = maxAmount(0, n - 1, arr);
        return res;
    }

//Driver Code Starts

    public static void Main() {
        int[] arr = {5, 3, 7, 10};
        int res = maximumAmount(arr);
        Console.WriteLine(res);
    }
}

//Driver Code Ends
JavaScript 
function maxAmount(i, j, arr) {
    // Base case: If i > j, no more elements are left to pick
    if (i > j)
        return 0;

    // Option 1: Take the first element arr[i]
    let takeFirst = arr[i] + Math.min(maxAmount(i + 2, j, arr),
                                      maxAmount(i + 1, j - 1, arr));

    // Option 2: Take the last element arr[j]
    let takeLast = arr[j] + Math.min(maxAmount(i + 1, j - 1, arr),
                                     maxAmount(i, j - 2, arr));

    return Math.max(takeFirst, takeLast);
}

function maximumAmount(arr) {
    let n = arr.length;
    let res = maxAmount(0, n - 1, arr);
    return res;
}


//Driver Code Starts

//Driver Code
let arr = [5, 3, 7, 10];
let res = maximumAmount(arr);
console.log(res);

//Driver Code Ends

Output
15

[Expected Approach 1] Using Top-Down DP (Memoization) – O(n*n) Time and O(n*n) Space

If we look carefully at the naive recursive approach, many subproblems are solved repeatedly, leading to redundant calculations and exponential time complexity. To overcome this, we use the memoization approach.

We create a 2D array dp[n][n], where n is the number of coins, and store the maximum amount that can be collected from the subarray arr[i…j]. Before computing, we check if dp[i][j] already contains a value. If it does, we simply return the stored result, avoiding unnecessary recursion.

C++ 
//Driver Code Starts
#include <iostream>
#include<vector>
using namespace std;

//Driver Code Ends

int maxAmount(int i, int j, vector<int> &arr, 
              vector<vector<int>> &dp) {

    // Base case: If i > j, no more elements
    // are left to pick
    if (i > j)
        return 0;

    // If the result is already computed, return
    // from the dp table
    if (dp[i][j] != -1)
        return dp[i][j];

    // Option 1: Take the first element arr[i]
    int takeFirst = arr[i] + min(maxAmount(i + 2, j, arr, dp), 
                                 maxAmount(i + 1, j - 1, arr, dp));

    // Option 2: Take the last element arr[j]
    int takeLast = arr[j] + min(maxAmount(i + 1, j - 1, arr, dp),
                                maxAmount(i, j - 2, arr, dp));

    // Store the maximum of the two choices
    return dp[i][j] = max(takeFirst, takeLast);
}

int maximumAmount(vector<int> &arr) {
  
  	int n = arr.size();

    vector<vector<int>> dp(n, vector<int>(n, -1));

    int res = maxAmount(0, n - 1, arr, dp);

    return res;
}

//Driver Code Starts

int main() {
  
    vector<int> arr = {5, 3, 7, 10};
    int res = maximumAmount(arr);
    cout << res << endl;

    return 0;
}
//Driver Code Ends
Java 
//Driver Code Starts
import java.util.Arrays;

public class GFG {

//Driver Code Ends

    static int maxAmount(int i, int j, int[] arr, int[][] dp) {
        // Base case: If i > j, no more elements
        // are left to pick
        if (i > j)
            return 0;

        // If the result is already computed, return
        // from the dp table
        if (dp[i][j] != -1)
            return dp[i][j];

        // Option 1: Take the first element arr[i]
        int takeFirst = arr[i] + Math.min(maxAmount(i + 2, j, arr, dp),
                                          maxAmount(i + 1, j - 1, arr, dp));

        // Option 2: Take the last element arr[j]
        int takeLast = arr[j] + Math.min(maxAmount(i + 1, j - 1, arr, dp),
                                         maxAmount(i, j - 2, arr, dp));

        // Store the maximum of the two choices
        return dp[i][j] = Math.max(takeFirst, takeLast);
    }

    static int maximumAmount(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][n];
        for (int[] row : dp) Arrays.fill(row, -1);
        int res = maxAmount(0, n - 1, arr, dp);
        return res;
    }

//Driver Code Starts

    public static void main(String[] args) {
        int[] arr = {5, 3, 7, 10};
        int res = maximumAmount(arr);
        System.out.println(res);
    }
}

//Driver Code Ends
Python 
def maxAmount(i, j, arr, dp):
    # Base case: If i > j, no more elements
    # are left to pick
    if i > j:
        return 0

    # If the result is already computed, return
    # from the dp table
    if dp[i][j] != -1:
        return dp[i][j]

    # Option 1: Take the first element arr[i]
    takeFirst = arr[i] + min(maxAmount(i + 2, j, arr, dp),
                             maxAmount(i + 1, j - 1, arr, dp))

    # Option 2: Take the last element arr[j]
    takeLast = arr[j] + min(maxAmount(i + 1, j - 1, arr, dp),
                            maxAmount(i, j - 2, arr, dp))

    # Store the maximum of the two choices
    dp[i][j] = max(takeFirst, takeLast)
    return dp[i][j]

def maximumAmount(arr):
    n = len(arr)
    dp = [[-1 for _ in range(n)] for _ in range(n)]
    res = maxAmount(0, n - 1, arr, dp)
    return res


#Driver Code Starts
if __name__ == "__main__":
    arr = [5, 3, 7, 10]
    res = maximumAmount(arr)
    print(res)

#Driver Code Ends
C# 
//Driver Code Starts
using System;

public class GFG{

//Driver Code Ends

    static int maxAmount(int i, int j, int[] arr, int[,] dp) {
        // Base case: If i > j, no more elements
        // are left to pick
        if (i > j)
            return 0;

        // If the result is already computed, return
        // from the dp table
        if (dp[i, j] != -1)
            return dp[i, j];

        // Option 1: Take the first element arr[i]
        int takeFirst = arr[i] + Math.Min(maxAmount(i + 2, j, arr, dp),
                                          maxAmount(i + 1, j - 1, arr, dp));

        // Option 2: Take the last element arr[j]
        int takeLast = arr[j] + Math.Min(maxAmount(i + 1, j - 1, arr, dp),
                                         maxAmount(i, j - 2, arr, dp));

        // Store the maximum of the two choices
        return dp[i, j] = Math.Max(takeFirst, takeLast);
    }

    static int maximumAmount(int[] arr) {
        int n = arr.Length;
        int[,] dp = new int[n, n];
        for (int x = 0; x < n; x++)
            for (int y = 0; y < n; y++)
                dp[x, y] = -1;

        int res = maxAmount(0, n - 1, arr, dp);
        return res;
    }

//Driver Code Starts

    public static void Main() {
        int[] arr = {5, 3, 7, 10};
        int res = maximumAmount(arr);
        Console.WriteLine(res);
    }
}

//Driver Code Ends
JavaScript 
function maxAmount(i, j, arr, dp) {
    // Base case: If i > j, no more elements
    // are left to pick
    if (i > j)
        return 0;

    // If the result is already computed, return
    // from the dp table
    if (dp[i][j] !== -1)
        return dp[i][j];

    // Option 1: Take the first element arr[i]
    let takeFirst = arr[i] + Math.min(maxAmount(i + 2, j, arr, dp),
                                      maxAmount(i + 1, j - 1, arr, dp));

    // Option 2: Take the last element arr[j]
    let takeLast = arr[j] + Math.min(maxAmount(i + 1, j - 1, arr, dp),
                                     maxAmount(i, j - 2, arr, dp));

    // Store the maximum of the two choices
    dp[i][j] = Math.max(takeFirst, takeLast);
    return dp[i][j];
}

function maximumAmount(arr) {
    let n = arr.length;
    let dp = Array.from({length: n}, () => Array(n).fill(-1));
    let res = maxAmount(0, n - 1, arr, dp);
    return res;
}


//Driver Code Starts

//Driver code
let arr = [5, 3, 7, 10];
let res = maximumAmount(arr);
console.log(res);

//Driver Code Ends

Output
15

[Expected Approach 2] Using Bottom-Up DP (Tabulation) – O(n*n) Time and O(n*n) Space

In this solution, we fill the DP table iteratively. First, we handle the base case:
If i == j, only one coin exists, so the player has no choice but to take it -> dp[i][j] = arr[i].
After filling these base values, we gradually solve larger subproblems. For every subarray arr[i…j], we have two choices:

  • Pick the ith coin: After that, the opponent plays optimally and leaves us the minimum possible value-> arr[i] + min(dp[i+2][j], dp[i+1][j-1])
  • Pick the jth coin: Again the opponent will make the move that minimizes our gain -> arr[j] + min(dp[i+1][j-1], dp[i][j-2])
C++ 
//Driver Code Starts
#include <iostream>
#include<vector>
using namespace std;

//Driver Code Ends

int maximumAmount(vector<int> &arr) {
    int n = arr.size();
    vector<vector<int>>dp(n, vector<int>(n,0));

    // Fill table using above
    // recursive formula.
    for (int gap = 0; gap < n; ++gap) {
        for (int i = 0, j = gap; j < n; ++i, ++j) {

            int x = ((i + 2) <= j) ? dp[i + 2][j] : 0;
            int y = ((i + 1) <= (j - 1)) ? dp[i + 1][j - 1] : 0;
            int z = (i <= (j - 2)) ? dp[i][j - 2] : 0;

            dp[i][j] = max(arr[i] + min(x, y), arr[j] + min(y, z));
        }
    }

    return dp[0][n - 1];
}

//Driver Code Starts

int main() {
    vector<int> arr = {5, 3, 7, 10};
    int res = maximumAmount(arr);
    cout << res;
    return 0;
}

//Driver Code Ends
Java 
import java.util.Arrays;

public class GFG {

    public static int maximumAmount(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][n];

        // Fill table using above
        // recursive formula.
        for (int gap = 0; gap < n; ++gap) {
            for (int i = 0, j = gap; j < n; ++i, ++j) {

                int x = ((i + 2) <= j) ? dp[i + 2][j] : 0;
                int y = ((i + 1) <= (j - 1)) ? dp[i + 1][j - 1] : 0;
                int z = (i <= (j - 2)) ? dp[i][j - 2] : 0;

                dp[i][j] = Math.max(arr[i] + Math.min(x, y), arr[j] + Math.min(y, z));
            }
        }

        return dp[0][n - 1];
    }

    public static void main(String[] args) {
        int[] arr = {5, 3, 7, 10};
        int res = maximumAmount(arr);
        System.out.println(res);
    }
}
Python 
def maximumAmount(arr):
    n = len(arr)
    dp = [[0] * n for _ in range(n)]

    # Fill table using above
    # recursive formula.
    for gap in range(n):
        for i in range(n - gap):
            j = i + gap

            x = dp[i + 2][j] if (i + 2) <= j else 0
            y = dp[i + 1][j - 1] if (i + 1) <= (j - 1) else 0
            z = dp[i][j - 2] if i <= (j - 2) else 0

            dp[i][j] = max(arr[i] + min(x, y), arr[j] + min(y, z))

    return dp[0][n - 1]


#Driver Code Starts

if __name__ == "__main__":
    arr = [5, 3, 7, 10]
    res = maximumAmount(arr)
    print(res)

#Driver Code Ends
C# 
//Driver Code Starts
using System;

class GFG {

//Driver Code Ends

    public static int maximumAmount(int[] arr) {
        int n = arr.Length;
        int[,] dp = new int[n, n];

        // Fill table using above
        // recursive formula.
        for (int gap = 0; gap < n; ++gap) {
            for (int i = 0, j = gap; j < n; ++i, ++j) {

                int x = ((i + 2) <= j) ? dp[i + 2, j] : 0;
                int y = ((i + 1) <= (j - 1)) ? dp[i + 1, j - 1] : 0;
                int z = (i <= (j - 2)) ? dp[i, j - 2] : 0;

                dp[i, j] = Math.Max(arr[i] + Math.Min(x, y), arr[j] + Math.Min(y, z));
            }
        }

        return dp[0, n - 1];
    }

//Driver Code Starts

    static void Main(string[] args) {
        int[] arr = { 5, 3, 7, 10 };
        int res = maximumAmount(arr);
        Console.WriteLine(res);
    }
}

//Driver Code Ends
JavaScript 
function maximumAmount(arr) {
    let n = arr.length;

    // Create a 2D dp array initialized with 0
    let dp = Array.from({ length: n }, () => Array(n).fill(0));

    // Fill table using above
    // recursive formula.
    for (let gap = 0; gap < n; ++gap) {
        for (let i = 0, j = gap; j < n; ++i, ++j) {

            let x = ((i + 2) <= j) ? dp[i + 2][j] : 0;
            let y = ((i + 1) <= (j - 1)) ? dp[i + 1][j - 1] : 0;
            let z = (i <= (j - 2)) ? dp[i][j - 2] : 0;

            dp[i][j] = Math.max(arr[i] + Math.min(x, y), arr[j] + Math.min(y, z));
        }
    }

    return dp[0][n - 1];
}


//Driver Code Starts
// Driver code
let arr = [5, 3, 7, 10];
let res = maximumAmount(arr);
console.log(res);

//Driver Code Ends

Output
15

[Space Optimised] O(n^2) Time and O(n) Space

In the previous approach, we used a 2D DP table. However, we can optimize this to a 1D DP array by observing that at every step we only need results from the current and previous ranges.

When the current player picks arr[i], their advantage becomes arr[i] – dp[j] because after this move the opponent plays optimally on the subarray (i+1…j) and dp[j] represents the lead the opponent can gain there. Similarly, if the player picks arr[j], their advantage becomes arr[j] – dp[j−1] since the opponent will now play on (i…j−1). Since we want to maximize our advantage we take the maximum of both.
At the end, dp[n-1] represents the maximum score difference the first player can guarantee over the opponent.

To convert this difference to the actual maximum coins collected,
we use: firstPlayerCoins= (totalSum + dp[n−1])/2
because totalSum = (first + second) and dp[n-1] = (first – second).

C++ 
//Driver Code Starts
#include <iostream>
#include<vector>
using namespace std;

//Driver Code Ends

int maximumAmount(vector<int> arr) {

    int n = arr.size();
    int sum = 0;
    vector<int> dp(n, 0);

    for (int i = (n - 1); i >= 0; i--) {
        
        // Calculating the sum of all the elements
        sum += arr[i];

        for (int j = i; j < n; j++) {
            if (i == j) {
                
                // If there is only one element
                dp[j] = arr[j];
            } else {
                // Calculating the dp states using the relation
                dp[j] = max(arr[i] - dp[j], arr[j] - dp[j - 1]);
            }
        }
    }

    // Return the final result
    return (sum + dp[n - 1]) / 2;
}

//Driver Code Starts

int main() {

    vector<int> arr = {5, 3, 7, 10};
    cout<<maximumAmount(arr);

    return 0;
}

//Driver Code Ends
Java 
//Driver Code Starts
import java.util.Arrays;

public class GFG {

//Driver Code Ends

    public static int maximumAmount(int[] arr) {

        int n = arr.length;
        int sum = 0;
        int[] dp = new int[n];

        for (int i = (n - 1); i >= 0; i--) {

            // Calculating the sum of all the elements
            sum += arr[i];

            for (int j = i; j < n; j++) {
                if (i == j) {

                    // If there is only one element
                    dp[j] = arr[j];
                } else {
                    // Calculating the dp states using the relation
                    dp[j] = Math.max(arr[i] - dp[j], arr[j] - dp[j - 1]);
                }
            }
        }

        // Return the final result
        return (sum + dp[n - 1]) / 2;
    }

//Driver Code Starts

    public static void main(String[] args) {
        int[] arr = {5, 3, 7, 10};
        System.out.println(maximumAmount(arr));
    }
}

//Driver Code Ends
Python 
def maximumAmount(arr):

    n = len(arr)
    sum_val = 0
    dp = [0] * n

    for i in range(n - 1, -1, -1):

        # Calculating the sum of all the elements
        sum_val += arr[i]

        for j in range(i, n):
            if i == j:

                # If there is only one element
                dp[j] = arr[j]
            else:
                # Calculating the dp states using the relation
                dp[j] = max(arr[i] - dp[j], arr[j] - dp[j - 1])

    # Return the final result
    return (sum_val + dp[n - 1]) // 2


#Driver Code Starts
if __name__ == "__main__":
    arr = [5, 3, 7, 10]
    print(maximumAmount(arr))

#Driver Code Ends
C# 
//Driver Code Starts
using System;
using System.Collections.Generic;

class GFG {

//Driver Code Ends

    static int maximumAmount(int[] arr) {

        int n = arr.Length;
        int sum = 0;
        int[] dp = new int[n];

        for (int i = (n - 1); i >= 0; i--) {

            // Calculating the sum of all the elements
            sum += arr[i];

            for (int j = i; j < n; j++) {
                if (i == j) {

                    // If there is only one element
                    dp[j] = arr[j];
                } else {
                    // Calculating the dp states using the relation
                    dp[j] = Math.Max(arr[i] - dp[j], arr[j] - dp[j - 1]);
                }
            }
        }

        // Return the final result
        return (sum + dp[n - 1]) / 2;
    }

//Driver Code Starts

    static void Main() {
        int[] arr = { 5, 3, 7, 10 };
        Console.WriteLine(maximumAmount(arr));
    }
}

//Driver Code Ends
JavaScript 
function maximumAmount(arr) {

    let n = arr.length;
    let sum = 0;
    let dp = new Array(n).fill(0);

    for (let i = n - 1; i >= 0; i--) {

        // Calculating the sum of all the elements
        sum += arr[i];

        for (let j = i; j < n; j++) {
            if (i === j) {

                // If there is only one element
                dp[j] = arr[j];
            } else {
                // Calculating the dp states using the relation
                dp[j] = Math.max(arr[i] - dp[j], arr[j] - dp[j - 1]);
            }
        }
    }

    // Return the final result
    return (sum + dp[n - 1]) / 2;
}


//Driver Code Starts
//Driver Code
let arr = [5, 3, 7, 10];
console.log(maximumAmount(arr));

//Driver Code Ends

Output
15


Comment

Explore