Coin Game

1int max_score(vector<int> coins, int l, int r) {
2    // Base case: If only one coin is present, return its value
3    if (l == r) {
4        return coins[r];
5    }
6
7    // Calculate the sum of the coins in the range [l, r]
8    int sum = 0;
9    for (int i = l; i <= r; i++) {
10        sum += coins[i];
11    }
12
13    // Calculate the score when choosing the leftmost or rightmost coin
14    int left_pick = max_score(coins, l + 1, r);
15    int right_pick = max_score(coins, l, r - 1);
16
17    // Return the best score after choosing the optimal coin
18    return sum - min(left_pick, right_pick);
19}
20
21int coin_game(vector<int> coins) {
22    int n = coins.size();
23    return max_score(coins, 0, n - 1);
24}
25

1public static int maxScore(List<Integer> coins, int l, int r) {
2    // Base case: If only one coin is present, return its value
3    if (l == r) {
4        return coins.get(r);
5    }
6
7    // Calculate the sum of the coins in the range [l, r]
8    int sum = 0;
9    for (int i = l; i <= r; i++) {
10        sum += coins.get(i);
11    }
12
13    // Calculate the score when choosing the leftmost or rightmost coin
14    int leftPick = maxScore(coins, l + 1, r);
15    int rightPick = maxScore(coins, l, r - 1);
16
17    // Return the best score after choosing the optimal coin
18    return sum - Math.min(leftPick, rightPick);
19}
20
21public static int coinGame(List<Integer> coins) {
22    int n = coins.size();
23    return maxScore(coins, 0, n - 1);
24}
25

1function maxScore(coins, l, r) {
2    // Base case: If only one coin is present, return its value
3    if (l === r) {
4        return coins[r];
5    }
6
7    // Calculate the sum of the coins in the range [l, r]
8    var sum = 0;
9    for (let i = l; i <= r; i++) {
10        sum += coins[i];
11    }
12
13    // Calculate the score when choosing the leftmost or rightmost coin
14    var leftPick = maxScore(coins, l + 1, r);
15    var rightPick = maxScore(coins, l, r - 1);
16
17    // Return the best score after choosing the optimal coin
18    return sum - Math.min(leftPick, rightPick);
19}
20
21function coinGame(coins) {
22    let n = coins.length;
23    return maxScore(coins, 0, n - 1);
24}
25

1int max_score(vector<vector<int>> &dp, vector<int> &prefix_sum, int l, int r) {
2    // Return memoized result
3    if (dp[l][r] != 0) {
4        return dp[l][r];
5    }
6
7    // Calculate total coins value from l to r
8    int sum = prefix_sum[r] - prefix_sum[l - 1];
9
10    // If only one coin is present, return its value
11    if (l == r) {
12        dp[l][r] = sum;
13    } else {
14        // Consider left and right coin and choose the better option
15        dp[l][r] = sum - min(max_score(dp, prefix_sum, l + 1, r), max_score(dp, prefix_sum, l, r - 1));
16    }
17
18    return dp[l][r];
19}
20
21int coin_game(vector<int> coins) {
22    int n = coins.size();
23
24    // Initialize the DP table with zeroes
25    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
26
27    // Compute prefix sum of coins
28    vector<int> prefix_sum(n + 1, 0);
29    for (int i = 1; i <= n; i++) {
30        prefix_sum[i] = prefix_sum[i - 1] + coins[i - 1];
31    }
32
33    return max_score(dp, prefix_sum, 1, n);
34}
35

1public static int maxScore(int[][] dp, int[] prefixSum, int l, int r) {
2    // Return memoized result
3    if (dp[l][r] != 0) {
4        return dp[l][r];
5    }
6
7    // Calculate total coins value from l to r
8    int sum = prefixSum[r] - prefixSum[l - 1];
9
10    // If only one coin is present, return its value
11    if (l == r) {
12        dp[l][r] = sum;
13    } else {
14        // Consider left and right coin and choose the better option
15        dp[l][r] = sum - Math.min(maxScore(dp, prefixSum, l + 1, r), maxScore(dp, prefixSum, l, r - 1));
16    }
17
18    return dp[l][r];
19}
20
21public static int coinGame(List<Integer> coins) {
22    int n = coins.size();
23    int[][] dp = new int[n + 1][n + 1];
24    int[] prefixSum = new int[n + 1];
25    prefixSum[0] = 0;
26    // Compute prefix sum of coins
27    for (int i = 1; i <= n; i++) {
28        prefixSum[i] = prefixSum[i - 1] + coins.get(i - 1);
29    }
30    
31    return maxScore(dp, prefixSum, 1, n);
32}
33

1function maxScore(dp, prefixSum, l, r) {
2    // Return memoized result
3    if (dp[l][r] != 0) {
4        return dp[l][r];
5    }
6
7    // Calculate total coins value from l to r
8    var sum = prefixSum[r] - prefixSum[l - 1];
9
10    // If only one coin is present, return its value
11    if (l == r) {
12        dp[l][r] = sum;
13    } else {
14        // Consider left and right coin and choose the better option
15        dp[l][r] = sum - Math.min(maxScore(dp, prefixSum, l + 1, r), maxScore(dp, prefixSum, l, r - 1));
16    }
17
18    return dp[l][r];
19}
20
21function coinGame(coins) {
22    let n = coins.length;
23    var dp = new Array(n + 1);
24
25    // Initialize everything to be zero
26    for (let i = 0; i <= n; i++) {
27        dp[i] = new Array(n + 1);
28        for (let j = 0; j <= n; j++) {
29            dp[i][j] = 0;   
30        }
31    }
32
33    // Compute prefix sum of coins
34    var prefixSum = new Array(n + 1);
35    prefixSum[0] = 0;
36    for (let i = 1; i <= n; i++) {
37        prefixSum[i] = prefixSum[i - 1] + coins[i - 1];
38    }
39    
40    return maxScore(dp, prefixSum, 1, n);
41}
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 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                // Base case: single coin
23                if (l == r) {
24                    dp[l][r] = prefix_sum[r] - prefix_sum[l - 1];
25                // General case: choose best between leftmost and rightmost coins
26                } else {
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

1function coinGame(coins) {
2    let n = coins.length;
3    // Compute prefix sums
4    var prefixSum = new Array(n + 1);
5    prefixSum[0] = 0;
6    for (let i = 1; i <= n; i++) {
7        prefixSum[i] = prefixSum[i - 1] + coins[i - 1];
8    }
9
10    // Initialize DP table
11    var dp = new Array(n + 1);
12    for (let i = 0; i <= n; i++) {
13        dp[i] = new Array(n + 1);
14        for (let j = 0; j <= n; j++) {
15            dp[i][j] = 0;
16        }
17    }
18    // Iterate over all intervals of the coins array
19    for (let size = 0; size < n; size++) {
20        for (let l = 1; l + size <= n; l++) {
21            let r = l + size;
22            // Base case: single coin
23            if (l == r) {
24                dp[l][r] = prefixSum[r] - prefixSum[l - 1];
25            } else {
26              // General case: choose best between leftmost and rightmost coins
27                dp[l][r] = prefixSum[r] - prefixSum[l - 1] - Math.min(dp[l + 1][r], dp[l][r - 1]);
28            }
29        }
30    }
31    return dp[1][n];
32}
33
34function splitWords(s) {
35    return s == "" ? [] : s.split(' ');
36}
37
38function* main() {
39    const coins = splitWords(yield).map((v) => parseInt(v));
40    const res = coinGame(coins);
41    console.log(res);
42}
43
44class EOFError extends Error {}
45{
46    const gen = main();
47    const next = (line) => gen.next(line).done && process.exit();
48    let buf = '';
49    next();
50    process.stdin.setEncoding('utf8');
51    process.stdin.on('data', (data) => {
52        const lines = (buf + data).split('\n');
53        buf = lines.pop();
54        lines.forEach(next);
55    });
56    process.stdin.on('end', () => {
57        buf && next(buf);
58        gen.throw(new EOFError());
59    });
60}
61

1#include <algorithm> // copy
2#include <iostream> // boolalpha, cin, cout
3#include <iterator> // back_inserter, istream_iterator
4#include <sstream> // istringstream
5#include <string> // getline, string
6#include <vector> // vector
7
8int coin_game(vector<int> coins) {
9    int n = coins.size();
10    // Compute prefix sums
11    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    vector<vector<int>> dp(n + 1, 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            // Base case: single coin
23            if (l == r) {
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] - 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