Optimal Strategy for a Game

Problem Statement

You are given an array of even number of coins arr[] with values. Two players take turns picking a coin from either end of the row. The player who collects more total value wins. Both players play optimally. Find the maximum value the first player can collect.

Example:

• Input: arr = [5, 3, 7, 10]

• Output: 15

• Explanation: Player 1 picks 10, Player 2 picks 7, Player 1 picks 5, Player 2 picks 3. Player 1 total = 10 + 5 = 15.

• Input: arr = [8, 15, 3, 7]

• Output: 22

• Explanation: Player 1 picks 7, Player 2 picks 8, Player 1 picks 15, Player 2 picks 3. Player 1 total = 7 + 15 = 22.

Noob-Friendly Explanation

Imagine coins are lined up in a row, and you and your friend take turns picking one coin from either the left end or the right end. Both of you are super smart and always make the best possible choice. You go first — what's the most money you can guarantee yourself?

The trick is that sometimes you pick a smaller coin now so you can get a bigger coin later. It's like chess — you think several moves ahead!

Approach 1: Brute Force (Recursion)

Intuition

The first player picks from either end. After that, the second player also plays optimally (picks the best for themselves). We recursively simulate all possibilities.

Algorithm

1. The current player picks from left or right.
2. The opponent then plays optimally on the remaining array.
3. The current player maximizes their total; the opponent minimizes what the current player can get next.

class Solution {
    public int optimalStrategy(int[] arr) {
        return solve(arr, 0, arr.length - 1);
    }

    private int solve(int[] arr, int i, int j) {
        if (i > j) return 0;
        if (i == j) return arr[i];

        // Pick left: opponent plays optimally on remaining
        int pickLeft = arr[i] + Math.min(
            solve(arr, i + 2, j),     // opponent picks left next
            solve(arr, i + 1, j - 1)  // opponent picks right next
        );

        // Pick right: opponent plays optimally on remaining
        int pickRight = arr[j] + Math.min(
            solve(arr, i + 1, j - 1),  // opponent picks left next
            solve(arr, i, j - 2)        // opponent picks right next
        );

        return Math.max(pickLeft, pickRight);
    }
}

Complexity Analysis

• Time Complexity: O(2^n) - Exponential branching at each step.
• Space Complexity: O(n) - Recursion stack depth.

Approach 2: Optimal (Dynamic Programming)

Intuition

We use a 2D DP table where dp[i][j] stores the maximum value the current player can collect from the subarray arr[i..j]. We fill the table for increasing subarray lengths.

Algorithm

1. Create dp[n][n]. Base case: dp[i][i] = arr[i] (only one coin, pick it).
2. For subarrays of length 2: dp[i][i+1] = max(arr[i], arr[i+1]).
3. For longer subarrays: the current player picks left or right and the opponent minimizes our next pick.
4. 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])).

class Solution {
    public int optimalStrategy(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][n];

        // Base case: single coin
        for (int i = 0; i < n; i++) {
            dp[i][i] = arr[i];
        }

        // Fill for increasing gap between i and j
        for (int gap = 1; gap < n; gap++) {
            for (int i = 0; i + gap < n; i++) {
                int j = i + gap;

                int pickLeft, pickRight;

                // Pick left coin arr[i]
                int a = (i + 2 <= j) ? dp[i + 2][j] : 0;
                int b = (i + 1 <= j - 1) ? dp[i + 1][j - 1] : 0;
                pickLeft = arr[i] + Math.min(a, b);

                // Pick right coin arr[j]
                int c = (i + 1 <= j - 1) ? dp[i + 1][j - 1] : 0;
                int d = (i <= j - 2) ? dp[i][j - 2] : 0;
                pickRight = arr[j] + Math.min(c, d);

                dp[i][j] = Math.max(pickLeft, pickRight);
            }
        }

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

Complexity Analysis

• Time Complexity: O(n^2) - We fill an n×n table, each cell in O(1).
• Space Complexity: O(n^2) - 2D DP table.