Facebook Pixel

Coin Game

Coin Game

You and a friend are playing a game with n coins arranged in a straight line, where each coin has a distinct value given by coins[i]. Starting with you, both players take turns, picking one coin from either end of the line and adding its value to their individual scores. Once a coin is picked up, it's removed from the line.

Given that your friend plays optimally to achieve the highest score, determine your maximum possible score.

Input

  • coins: A list of the coins.

Output

Your maximum possible score, provided that you go first and your friend plays perfectly.

Examples

Example 1:

Input:

coins = [4, 4, 9, 4]

Output: 13

Explanation:

The coins start like this:

4, 4, 9, 4

You always go first, so you take the 4 from the left side:

4, 9, 4

Your friend takes any of the 4s (it doesn't matter)

9, 4

Now you take the 9, and your friend takes the remaining 4.

Your score in this case, is 4 + 9 = 13.

Constraints

  • 1 <= len(coins) <= 1000
  • 1 <= coins[i] <= 5 * 10^5

Try it yourself

Solution

Brute Force

A brute force solution would enumerate through all possibilities. For each of the n turns, we either choose the left-most coin or the right-most coin and check which option maximizes our score.

The 2 cases mentioned above are described as follows:

  • Case 1: We take coin l
    • Coins in the range [l + 1, r] are left
    • Since our opponent plays optimally, they will gain points equal to maxScore(l + 1, r)
    • Since we get all other coins, our score will be sum(l, r) - maxScore(l + 1, r)
  • Case 2: We take coin r
    • Coins in range [l, r - 1] are left
    • Since our opponent plays optimally, they will gain points equal to maxScore(l, r - 1)
    • Since we get all other coins, our score will be sum(l, r) - maxScore(l, r - 1)

Next, we choose the case that gives us the greatest score, or minimizes the opponent's score. Therefore, the solution is either:

  • maxScore(l, r) = max(sum(l, r) - maxScore(l + 1, r), sum(l, r) - maxscore(l, r - 1)) or
  • maxScore(l, r) = sum(l, r) - min(maxScore(l + 1, r), maxScore(l, r - 1))

Note that a common pitfall is to try to keep tracking of which player the current recursive call is for using an extra state variable. This is unnecessary because it doesn't really matter which user the recursive call is for because the current player always tries to minimize the other player's score (each user "plays perfectly in such a way that maximizes their score"). Each recursive call returns the best possible score the current player can get. The outermost call will return the best score for the first player.

Since there are n turns, 2 possibilities each turn, and takes O(n) to calculate the sum from l to r, the final runtime is O(n * 2^n).

Here's a visual representation of the idea:

First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide
First slide

The following is an implementation of the idea above:

1from typing import List
2
3def max_score(coins: List[int], l: int, r: int) -> int:
4    # Base case: If only one coin is present, return its value
5    if l == r:
6        return coins[r]
7
8    # Calculate the sum of the coins in the range [l, r]
9    total = 0
10    for i in range(l, r + 1):
11        total += coins[i]
12
13    # Calculate the score when choosing the leftmost or rightmost coin
14    left_pick = max_score(coins, l + 1, r)
15    right_pick = max_score(coins, l, r - 1)
16
17    # Return the best score after choosing the optimal coin
18    return total - min(left_pick, right_pick)
19
20def coin_game(coins: List[int]) -> int:
21    n = len(coins)
22    return max_score(coins, 0, n - 1)
23
24if __name__ == "__main__":
25    coins = [int(x) for x in input().split()]
26    res = coin_game(coins)
27    print(res)
28
1import java.util.Arrays;
2import java.util.List;
3import java.util.Scanner;
4import java.util.stream.Collectors;
5
6class Solution {
7    public static int maxScore(List<Integer> coins, int l, int r) {
8        // Base case: If only one coin is present, return its value
9        if (l == r) {
10            return coins.get(r);
11        }
12
13        // Calculate the sum of the coins in the range [l, r]
14        int sum = 0;
15        for (int i = l; i <= r; i++) {
16            sum += coins.get(i);
17        }
18
19        // Calculate the score when choosing the leftmost or rightmost coin
20        int leftPick = maxScore(coins, l + 1, r);
21        int rightPick = maxScore(coins, l, r - 1);
22
23        // Return the best score after choosing the optimal coin
24        return sum - Math.min(leftPick, rightPick);
25    }
26
27    public static int coinGame(List<Integer> coins) {
28        int n = coins.size();
29        return maxScore(coins, 0, n - 1);
30    }
31
32    public static List<String> splitWords(String s) {
33        return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
34    }
35
36    public static void main(String[] args) {
37        Scanner scanner = new Scanner(System.in);
38        List<Integer> coins = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
39        scanner.close();
40        int res = coinGame(coins);
41        System.out.println(res);
42    }
43}
44
1"use strict";
2
3function maxScore(coins, l, r) {
4    // Base case: If only one coin is present, return its value
5    if (l === r) {
6        return coins[r];
7    }
8
9    // Calculate the sum of the coins in the range [l, r]
10    let sum = 0;
11    for (let i = l; i <= r; i++) {
12        sum += coins[i];
13    }
14
15    // Calculate the score when choosing the leftmost or rightmost coin
16    const leftPick = maxScore(coins, l + 1, r);
17    const rightPick = maxScore(coins, l, r - 1);
18
19    // Return the best score after choosing the optimal coin
20    return sum - Math.min(leftPick, rightPick);
21}
22
23function coinGame(coins) {
24    const n = coins.length;
25    return maxScore(coins, 0, n - 1);
26}
27
28function splitWords(s) {
29    return s === "" ? [] : s.split(" ");
30}
31
32function* main() {
33    const coins = splitWords(yield).map((v) => parseInt(v));
34    const res = coinGame(coins);
35    console.log(res);
36}
37
38class EOFError extends Error {}
39{
40    const gen = main();
41    const next = (line) => gen.next(line).done && process.exit();
42    let buf = "";
43    next();
44    process.stdin.setEncoding("utf8");
45    process.stdin.on("data", (data) => {
46        const lines = (buf + data).split("\n");
47        buf = lines.pop();
48        lines.forEach(next);
49    });
50    process.stdin.on("end", () => {
51        buf && next(buf);
52        gen.throw(new EOFError());
53    });
54}
55
1#include <algorithm>
2#include <iostream>
3#include <iterator>
4#include <sstream>
5#include <string>
6#include <vector>
7
8int max_score(std::vector<int>& coins, int l, int r) {
9    // Base case: If only one coin is present, return its value
10    if (l == r) {
11        return coins[r];
12    }
13
14    // Calculate the sum of the coins in the range [l, r]
15    int sum = 0;
16    for (int i = l; i <= r; i++) {
17        sum += coins[i];
18    }
19
20    // Calculate the score when choosing the leftmost or rightmost coin
21    int left_pick = max_score(coins, l + 1, r);
22    int right_pick = max_score(coins, l, r - 1);
23
24    // Return the best score after choosing the optimal coin
25    return sum - std::min(left_pick, right_pick);
26}
27
28int coin_game(std::vector<int>& coins) {
29    int n = coins.size();
30    return max_score(coins, 0, n - 1);
31}
32
33template<typename T>
34std::vector<T> get_words() {
35    std::string line;
36    std::getline(std::cin, line);
37    std::istringstream ss{line};
38    ss >> std::boolalpha;
39    std::vector<T> v;
40    std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
41    return v;
42}
43
44int main() {
45    std::vector<int> coins = get_words<int>();
46    int res = coin_game(coins);
47    std::cout << res << '\n';
48}
49

Slight Optimization

So far, for each recursive call we are spending O(n) time to calculate the sum between the range [l, r]. However, instead of using O(n) every time we need the sum we can use a prefix sum array to get the range sum in O(1) time and a single O(n) pre-computation.

1
1
1int max_score(vector<int> coins, int l, int r) {
2
+
1  int sum = coins[r] - coins[l - 1]; // query sum from [l, r] in O(1)
2
3
1  if (l == r) {
3
-
1    return coins[r];
4
+
1    return sum;
4
5
1  }
5
6
6
-
1  int sum = 0;
7
-
1  for (int i = l; i <= r; i++) {
8
-
1    sum += coins[i];
9
-
1  }
10
-
1 
11
7
1  int left_pick = max_score(coins, l + 1, r);
12
8
1  int right_pick = max_score(coins, l, r - 1);
13
9
1  return sum - min(left_pick, right_pick);
14
10
1}
15
11
1int coin_game(vector<int> coins) {
16
12
1  int n = coins.size();
17
-
1  return max_score(coins, 0, n - 1);
13
+
1  vector<int> prefix_sum(n + 1, 0); // precompute prefix sum
14
+
1  for (int i = 1; i <= n; i++) {
15
+
1    prefix_sum[i] = prefix_sum[i - 1] + coins[i -1];
16
+
1  }
17
+
18
+
1  return max_score(prefix_sum, 1, n);
18
19
1}
1
1
1public static int maxScore(List<Integer> coins, int l, int r) {
2
+
1  int sum = coins.get(r) - coins.get(l - 1); // query sum from [l, r] in O(1)
2
3
1  if (l == r) {
3
-
1    return coins.get(r);
4
+
1    return sum;
4
5
1  }
5
-
1  int sum = 0;
6
-
1  for (int i = l; i <= r; i++) {
7
-
1    sum += coins.get(i);
8
-
1  }
9
-
1 
10
6
1  int leftPick = maxScore(coins, l + 1, r);
11
7
1  int rightPick = maxScore(coins, l, r - 1);
12
8
1  return sum - Math.min(leftPick, rightPick);
13
9
1}
14
10
1public static int coinGame(List<Integer> coins) {
15
11
1  int n = coins.size();
16
-
1  return maxScore(coins, 0, n - 1);
12
+
1  List<Integer> prefixSum = new ArrayList<>(); // precompute prefix sums
13
+
1  prefixSum.add(0);
14
+
1  for (int i = 1; i <= n; i++) {
15
+
1    prefixSum.add(prefixSum.get(i - 1) + coins.get(i - 1));
16
+
1  }
17
+
1  return maxScore(prefixSum, 1, n);
17
18
1}
1
1
1function maxScore(coins, l, r) {
2
+
1  var sum = coins[r] - coins[l - 1];
2
3
1  if (l === r) {
3
-
1    return coins[r];
4
+
1    return sum;
4
5
1  }
5
6
6
-
1  var sum = 0;
7
-
1  for (let i = l; i <= r; i++) {
8
-
1    sum += coins[i];
9
-
1  }
10
-
1 
11
7
1  var leftPick = maxScore(coins, l + 1, r);
12
8
1  var rightPick = maxScore(coins, l, r - 1);
13
9
1  return sum - Math.min(leftPick, rightPick);
14
10
1}
Expand 1 lines ...
16
12
1function coinGame(coins) {
17
13
1  let n = coins.length;
18
-
1  return maxScore(coins, 0, n - 1);
14
+
1  var prefixSum = [0];
15
+
1  for (let i = 1; i <= n; i++) {
16
+
1    prefixSum.push(prefixSum[i - 1] + coins[i - 1]);
17
+
1  }
18
+
1  return maxScore(prefixSum, 1, n);
19
19
1}
1
1
1def max_score(coins, l, r):
2
+
1  sum = coins[r] - coins[l - 1] # query sum from [l, r] in O(1)
2
3
1  if l == r:
3
-
1    return coins[r]
4
+
1    return sum
4
5
5
6
6
-
1  sum = 0
7
-
1  for i in range(l, r + 1):
8
-
1    sum += coins[i]
9
-
1 
10
7
1  left_pick = max_score(coins, l + 1, r)
11
8
1  right_pick = max_score(coins, l, r - 1)
12
9
1  return sum - min(left_pick, right_pick)
13
10
1def coin_game(coins):
14
11
1  n = len(coins)
15
-
1  return max_score(coins, 0, n - 1)
12
+
1  prefix_sum = [0 for i in range(n + 1)] # precompute prefix sum
13
+
1  for i in range(1, n + 1):
14
+
1    prefix_sum[i] = prefix_sum[i - 1] + coins[i - 1]
15
+
1  return max_score(prefix_sum, 1, n)
Top-down DP


In essence, the DP top-down solution is the brute force solution with memoization. You may have noticed maxScore(l, r) can be be memoized.


Let’s formalize our idea above by specifying our DP state (i.e. what’s important that can lead us to our answer). In this case, let dp(l, r) be the maximum score we can achieve if coins in the range [l, r] are the only ones present and we go first.


Furthermore, our base case is: dp(l, r) = v_r if l = r. That is, since the range contains only one coin, we simply take that coin.


Now we deal with the transition. Exactly like our brute force solution, we consider two cases of picking either the left or right coin.


Next, we choose the case that gives us the greatest score or minimizes the opponent's score. Therefore, the solution is either:


    

  • dp(l, r) = max(sum(l, r) - dp(l + 1, r), sum(l, r) - dp(l, r - 1)) or
    • 

  • dp(l, r) = sum(l, r) - min(dp(l + 1, r), dp(l, r - 1))
    • 

The following is a top-down solution to the problem:
1import sys
2from typing import List
3
4sys.setrecursionlimit(1500)
5
6def max_score(dp: List[List[int]], prefix_sum: List[int], l: int, r: int) -> int:
7    # Return memoized result
8    if dp[l][r] != 0:
9        return dp[l][r]
10
11    # Calculate total coins value from l to r
12    total = prefix_sum[r] - prefix_sum[l - 1]
13
14    # If only one coin is present, return its value
15    if l == r:
16        dp[l][r] = total
17    else:
18        # Consider left and right coin and choose the better option
19        dp[l][r] = total - min(
20            max_score(dp, prefix_sum, l + 1, r),
21            max_score(dp, prefix_sum, l, r - 1),
22        )
23
24    return dp[l][r]
25
26def coin_game(coins: List[int]) -> int:
27    n = len(coins)
28    # Initialize the DP table with zeroes
29    dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
30
31    # Compute prefix sum of coins
32    prefix_sum = [0 for i in range(n + 1)]
33    for i in range(1, n + 1):
34        prefix_sum[i] = prefix_sum[i - 1] + coins[i - 1]
35
36    return max_score(dp, prefix_sum, 1, n)
37
38if __name__ == "__main__":
39    coins = [int(x) for x in input().split()]
40    res = coin_game(coins)
41    print(res)
42
1import java.util.Arrays;
2import java.util.List;
3import java.util.Scanner;
4import java.util.stream.Collectors;
5
6class Solution {
7    public static int maxScore(int[][] dp, int[] prefixSum, int l, int r) {
8        // Return memoized result
9        if (dp[l][r] != 0) {
10            return dp[l][r];
11        }
12
13        // Calculate total coins value from l to r
14        int sum = prefixSum[r] - prefixSum[l - 1];
15
16        // If only one coin is present, return its value
17        if (l == r) {
18            dp[l][r] = sum;
19        } else {
20            // Consider left and right coin and choose the better option
21            dp[l][r] = sum - Math.min(maxScore(dp, prefixSum, l + 1, r), maxScore(dp, prefixSum, l, r - 1));
22        }
23
24        return dp[l][r];
25    }
26
27    public static int coinGame(List<Integer> coins) {
28        int n = coins.size();
29        int[][] dp = new int[n + 1][n + 1];
30        int[] prefixSum = new int[n + 1];
31        prefixSum[0] = 0;
32        // Compute prefix sum of coins
33        for (int i = 1; i <= n; i++) {
34            prefixSum[i] = prefixSum[i - 1] + coins.get(i - 1);
35        }
36
37        return maxScore(dp, prefixSum, 1, n);
38    }
39
40    public static List<String> splitWords(String s) {
41        return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
42    }
43
44    public static void main(String[] args) {
45        Scanner scanner = new Scanner(System.in);
46        List<Integer> coins = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
47        scanner.close();
48        int res = coinGame(coins);
49        System.out.println(res);
50    }
51}
52
1"use strict";
2
3function maxScore(dp, prefixSum, l, r) {
4    // Return memoized result
5    if (dp[l][r] !== 0) {
6        return dp[l][r];
7    }
8
9    // Calculate total coins value from l to r
10    const sum = prefixSum[r] - prefixSum[l - 1];
11
12    // If only one coin is present, return its value
13    if (l === r) {
14        dp[l][r] = sum;
15    } else {
16        // Consider left and right coin and choose the better option
17        dp[l][r] = sum - Math.min(maxScore(dp, prefixSum, l + 1, r), maxScore(dp, prefixSum, l, r - 1));
18    }
19
20    return dp[l][r];
21}
22
23function coinGame(coins) {
24    const n = coins.length;
25    const dp = new Array(n + 1);
26
27    // Initialize everything to be zero
28    for (let i = 0; i <= n; i++) {
29        dp[i] = new Array(n + 1);
30        for (let j = 0; j <= n; j++) {
31            dp[i][j] = 0;
32        }
33    }
34
35    // Compute prefix sum of coins
36    const prefixSum = new Array(n + 1);
37    prefixSum[0] = 0;
38    for (let i = 1; i <= n; i++) {
39        prefixSum[i] = prefixSum[i - 1] + coins[i - 1];
40    }
41
42    return maxScore(dp, prefixSum, 1, n);
43}
44
45function splitWords(s) {
46    return s === "" ? [] : s.split(" ");
47}
48
49function* main() {
50    const coins = splitWords(yield).map((v) => parseInt(v));
51    const res = coinGame(coins);
52    console.log(res);
53}
54
55class EOFError extends Error {}
56{
57    const gen = main();
58    const next = (line) => gen.next(line).done && process.exit();
59    let buf = "";
60    next();
61    process.stdin.setEncoding("utf8");
62    process.stdin.on("data", (data) => {
63        const lines = (buf + data).split("\n");
64        buf = lines.pop();
65        lines.forEach(next);
66    });
67    process.stdin.on("end", () => {
68        buf && next(buf);
69        gen.throw(new EOFError());
70    });
71}
72
1#include <algorithm>
2#include <iostream>
3#include <iterator>
4#include <sstream>
5#include <string>
6#include <vector>
7
8int max_score(std::vector<std::vector<int>>& dp, std::vector<int>& prefix_sum, int l, int r) {
9    // Return memoized result
10    if (dp[l][r] != 0) {
11        return dp[l][r];
12    }
13
14    // Calculate total coins value from l to r
15    int sum = prefix_sum[r] - prefix_sum[l - 1];
16
17    // If only one coin is present, return its value
18    if (l == r) {
19        dp[l][r] = sum;
20    } else {
21        // Consider left and right coin and choose the better option
22        dp[l][r] = sum - std::min(max_score(dp, prefix_sum, l + 1, r), max_score(dp, prefix_sum, l, r - 1));
23    }
24
25    return dp[l][r];
26}
27
28int coin_game(std::vector<int> coins) {
29    int n = coins.size();
30
31    // Initialize the DP table with zeroes
32    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(n + 1, 0));
33
34    // Compute prefix sum of coins
35    std::vector<int> prefix_sum(n + 1, 0);
36    for (int i = 1; i <= n; i++) {
37        prefix_sum[i] = prefix_sum[i - 1] + coins[i - 1];
38    }
39
40    return max_score(dp, prefix_sum, 1, n);
41}
42
43template<typename T>
44std::vector<T> get_words() {
45    std::string line;
46    std::getline(std::cin, line);
47    std::istringstream ss{line};
48    ss >> std::boolalpha;
49    std::vector<T> v;
50    std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
51    return v;
52}
53
54int main() {
55    std::vector<int> coins = get_words<int>();
56    int res = coin_game(coins);
57    std::cout << res << '\n';
58}
59
Bottom-up DP


The iterative version is a bit trickier. The idea is that we loop through all the
possible lengths starting from 1 to n. Then for each size, we consider all possible
left starting positions and calculate the respective right ending position. We do it in
this order because we are building solutions from the smallest case and building the
solutions up. That is, first considering each item as an interval of length 1 then
merging their solutions together to form larger and larger interval lengths until we get
to an interval of size n.


Note: There are slight tweaks in the implementation of this idea such as how we loop
through the lengths.


Here's a visualization of the table generated:


Coin game, interval DP, bottom-up DP
And here's the bottom-up iterative code:
1from typing import List
2
3def coin_game(coins: List[int]) -> int:
4    n = len(coins)
5    # Compute prefix sums
6    prefix_sum = [0 for i in range(n + 1)]
7    for i in range(1, n + 1):
8        prefix_sum[i] = prefix_sum[i - 1] + coins[i - 1]
9
10    # Initialize DP table
11    dp = [[0 for i in range(n + 1)] for j in range(n + 1)]
12
13    # Iterate over all intervals of the coins array
14    for size in range(n):
15        for l in range(1, n - size + 1):
16            r = l + size
17            if l == r:
18                # Base case: single coin
19                dp[l][r] = prefix_sum[r] - prefix_sum[l - 1]
20            else:
21                # General case: choose best between leftmost and rightmost coins
22                dp[l][r] = prefix_sum[r] - prefix_sum[l - 1] - min(dp[l + 1][r], dp[l][r - 1])
23    return dp[1][n]
24
25if __name__ == "__main__":
26    coins = [int(x) for x in input().split()]
27    res = coin_game(coins)
28    print(res)
29
1import java.util.Arrays;
2import java.util.List;
3import java.util.Scanner;
4import java.util.stream.Collectors;
5
6class Solution {
7    public static int coinGame(List<Integer> coins) {
8        int n = coins.size();
9        // Compute prefix sums
10        int[] prefix_sum = new int[n + 1];
11        prefix_sum[0] = 0;
12        for (int i = 1; i <= n; i++) {
13            prefix_sum[i] = prefix_sum[i - 1] + coins.get(i - 1);
14        }
15
16        // Initialize DP table
17        int[][] dp = new int[n + 1][n + 1];
18        // Iterate over all intervals of the coins array
19        for (int size = 0; size < n; size++) {
20            for (int l = 1; l + size <= n; l++) {
21                int r = l + size;
22                if (l == r) {
23                    // Base case: single coin
24                    dp[l][r] = prefix_sum[r] - prefix_sum[l - 1];
25                } else {
26                    // General case: choose best between leftmost and rightmost coins
27                    dp[l][r] = prefix_sum[r] - prefix_sum[l - 1] - Math.min(dp[l + 1][r], dp[l][r - 1]);
28                }
29            }
30        }
31        return dp[1][n];
32    }
33
34    public static List<String> splitWords(String s) {
35        return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
36    }
37
38    public static void main(String[] args) {
39        Scanner scanner = new Scanner(System.in);
40        List<Integer> coins = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
41        scanner.close();
42        int res = coinGame(coins);
43        System.out.println(res);
44    }
45}
46
1"use strict";
2
3function coinGame(coins) {
4    const n = coins.length;
5    // Compute prefix sums
6    const prefixSum = new Array(n + 1);
7    prefixSum[0] = 0;
8    for (let i = 1; i <= n; i++) {
9        prefixSum[i] = prefixSum[i - 1] + coins[i - 1];
10    }
11
12    // Initialize DP table
13    const dp = new Array(n + 1);
14    for (let i = 0; i <= n; i++) {
15        dp[i] = new Array(n + 1);
16        for (let j = 0; j <= n; j++) {
17            dp[i][j] = 0;
18        }
19    }
20    // Iterate over all intervals of the coins array
21    for (let size = 0; size < n; size++) {
22        for (let l = 1; l + size <= n; l++) {
23            const r = l + size;
24            if (l === r) {
25                // Base case: single coin
26                dp[l][r] = prefixSum[r] - prefixSum[l - 1];
27            } else {
28                // General case: choose best between leftmost and rightmost coins
29                dp[l][r] = prefixSum[r] - prefixSum[l - 1] - Math.min(dp[l + 1][r], dp[l][r - 1]);
30            }
31        }
32    }
33    return dp[1][n];
34}
35
36function splitWords(s) {
37    return s === "" ? [] : s.split(" ");
38}
39
40function* main() {
41    const coins = splitWords(yield).map((v) => parseInt(v));
42    const res = coinGame(coins);
43    console.log(res);
44}
45
46class EOFError extends Error {}
47{
48    const gen = main();
49    const next = (line) => gen.next(line).done && process.exit();
50    let buf = "";
51    next();
52    process.stdin.setEncoding("utf8");
53    process.stdin.on("data", (data) => {
54        const lines = (buf + data).split("\n");
55        buf = lines.pop();
56        lines.forEach(next);
57    });
58    process.stdin.on("end", () => {
59        buf && next(buf);
60        gen.throw(new EOFError());
61    });
62}
63
1#include <algorithm>
2#include <iostream>
3#include <iterator>
4#include <sstream>
5#include <string>
6#include <vector>
7
8int coin_game(std::vector<int> coins) {
9    int n = coins.size();
10    // Compute prefix sums
11    std::vector<int> prefix_sum(n + 1, 0);
12    for (int i = 1; i <= n; i++) {
13        prefix_sum[i] = prefix_sum[i - 1] + coins[i - 1];
14    }
15
16    // Initialize DP table
17    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(n + 1, 0));
18    // Iterate over all intervals of the coins array
19    for (int size = 0; size < n; size++) {
20        for (int l = 1; l + size <= n; l++) {
21            int r = l + size;
22            if (l == r) {
23                // Base case: single coin
24                dp[l][r] = prefix_sum[r] - prefix_sum[l - 1];
25            } else {
26                // General case: choose best between leftmost and rightmost coins
27                dp[l][r] = prefix_sum[r] - prefix_sum[l - 1] - std::min(dp[l + 1][r], dp[l][r - 1]);
28            }
29        }
30    }
31    return dp[1][n];
32}
33
34template<typename T>
35std::vector<T> get_words() {
36    std::string line;
37    std::getline(std::cin, line);
38    std::istringstream ss{line};
39    ss >> std::boolalpha;
40    std::vector<T> v;
41    std::copy(std::istream_iterator<T>{ss}, std::istream_iterator<T>{}, std::back_inserter(v));
42    return v;
43}
44
45int main() {
46    std::vector<int> coins = get_words<int>();
47    int res = coin_game(coins);
48    std::cout << res << '\n';
49}
50
Time Complexity: O(n^2) for the nested for loops.

Space Complexity: O(n) as we use a 2d dp table.
Invest in Yourself
Your new job is waiting. 83% of people that complete the program get a job offer. Unlock unlimited access to all content and features.
Go Pro
Favorite (idle)