Maximum Number Of Coins You Can Get - Leetcode Solution

Problem Statement:

You have an array of coins and two players, Alice and Bob, take turns selecting a coin from either end of the array. Each player wants to maximize the value of coins they obtain. Return the maximum number of coins that Alice can obtain.

Example 1: Input: [2,4,1,2,7,8] Output: 9 Explanation: Alice takes 2 --> Bob takes 8 Alice takes 4 --> Bob takes 7 Alice takes 2 --> Bob takes 1 Alice takes 8 --> Alice takes 2 Alice obtains 2 + 4 + 2 + 1 = 9 coins.

Approach:

This problem can be solved using dynamic programming. We can create a 2-D array "dp" of size n x n, where n is the length of the given array. dp[i][j] represents the maximum number of coins Alice can obtain if the coins in the array between indices i and j (inclusive) are available.

We can fill the dp array from left to right, considering all possible intervals of the given array. For each interval, we have two options:

1. Alice chooses the ith coin and Bob chooses the jth coin.
2. Alice chooses the jth coin and Bob chooses the ith coin.

We can iterate through all possible intervals and fill the dp array accordingly. The base cases for the dp array are:

1. dp[i][i] = coins[i], because only one coin is available in this case.
2. dp[i][i+1] = max(coins[i], coins[i+1]), because only two coins are available in this case.

Finally, the maximum number of coins that Alice can obtain is stored in dp[0][n-1].

Solution:

Here is the Python code to solve this problem using dynamic programming:

class Solution: def maxCoins(self, coins: List[int]) -> int: n = len(coins) dp = [[0 for _ in range(n)] for _ in range(n)] for l in range(1, n + 1): for i in range(n - l + 1): j = i + l - 1 if i == j: dp[i][j] = coins[i] elif i + 1 == j: dp[i][j] = max(coins[i], coins[j]) else: dp[i][j] = max(coins[i] + min(dp[i+2][j], dp[i+1][j-1]), coins[j] + min(dp[i+1][j-1], dp[i][j-2])) return dp[0][n-1]

Time Complexity: O(n^2)

Space Complexity: O(n^2)

1