Problem

In front of you is a row of N coins, with values v_1, v_2, ..., v_n.

You are asked to play the following game. You and an opponent take turns choosing either the first or last coin from the row, removing it from the row, and receiving the value of the coin.

Write a program that returns the maximum amount of money you can win with certainty, if you move first, assuming your opponent plays optimally.

Examples

Example 1

1
2
3
4
5

Input: nums = [1, 2, 3, 4]
Output: 6
Explanation: 
- You pick 4 (first move), opponent picks 3, then you pick 2.
- Your score = 4 + 2 = 6, opponent's score = 3 + 1 = 4.

Example 2

1
2
3
4
5

Input: nums = [8, 15, 3, 7]
Output: 22
Explanation: 
- You pick 7 (first move), opponent picks 15, then you pick 8.
- Your score = 7 + 8 = 22, opponent's score = 15 + 3 = 18.

Solution

Method 1 - Using DP

  1. To win the maximum amount, you need to consider both your turn and your opponent’s turn simultaneously, anticipating their move. Hence, this is a dynamic programming problem, not a simple greedy one.
  2. Instead of choosing the coin greedily, you must evaluate both options (first coin or last coin) and simulate the opponent’s optimal choice to assess the best possible move at every step.
  3. Use the following recurrence relation to compute the optimal score:
    • dp[i][j] represents the maximum amount you can collect when considering coins from index i to j:
    • If you pick the first coin: dp[i][j] = nums[i] + min(dp[i+2][j], dp[i+1][j-1])
    • If you pick the last coin: dp[i][j] = nums[j] + min(dp[i+1][j-1], dp[i][j-2])
    • The min part represents that your opponent plays optimally to reduce your score.
  4. The base cases are:
    • When there is only one coin left: dp[i][i] = nums[i].

Approach

  1. Use a 2D dp array where dp[i][j] stores the maximum value you can secure from coins between indices i and j.
  2. Build the table dp iteratively, starting with the smallest sub-problems:
    • For diagonal elements (one coin), dp[i][i] = nums[i].
    • For two coins, choose the maximum: dp[i][j] = max(nums[i], nums[j]).
  3. For larger subarrays, evaluate using the above recurrence relation.
  4. Finally, return dp[0][n-1], representing the best value you can collect for the whole array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution {

    public int maxCoins(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][n];

        // Fill the dp table
        for (int length = 1; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                // Base cases
                if (i == j) {
                    dp[i][j] = nums[i];
                } else {
                    int leftPick =
                        nums[i] +
                        Math.min(
                            i + 2 <= j ? dp[i + 2][j] : 0,
                            i + 1 <= j - 1 ? dp[i + 1][j - 1] : 0
                        );
                    int rightPick =
                        nums[j] +
                        Math.min(
                            i + 1 <= j - 1 ? dp[i + 1][j - 1] : 0,
                            i <= j - 2 ? dp[i][j - 2] : 0
                        );
                    dp[i][j] = Math.max(leftPick, rightPick);
                }
            }
        }
        return dp[0][n - 1];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = { 8, 15, 3, 7 };
        System.out.println(solution.maxCoins(nums)); // Output: 22
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution:
    def maxCoins(self, nums):
        n = len(nums)
        # Initialize dp array
        dp = [[0] * n for _ in range(n)]
        
        # Fill the dp array
        for length in range(1, n+1):  # Subarrays of length 1 to n
            for i in range(n - length + 1):
                j = i + length - 1
                # Base cases
                if i == j:
                    dp[i][j] = nums[i]
                else:
                    # Calculate dp[i][j] using the recurrence relation
                    left_pick = nums[i] + min(dp[i+2][j] if i+2 <= j else 0, 
                                        dp[i+1][j-1] if i+1 <= j-1 else 0)
                    right_pick = nums[j] + min(dp[i+1][j-1] if i+1 <= j-1 else 0, 
                                            dp[i][j-2] if i <= j-2 else 0)
                    dp[i][j] = max(left_pick, right_pick)
        
        return dp[0][n-1]


# Example usage
nums = [8, 15, 3, 7]
print(Solution().maxCoins(nums))  # Output: 22

Complexity

  • ⏰ Time complexity: O(n^2): We fill an n x n table.
  • 🧺 Space complexity: O(n^2): The 2D dp array stores results for all subarrays.