Optimal Strategy For A Game

Medium
1607.

Optimal Strategy For A Game

Optimal Strategy For A Game is a medium coding problem on arrays, dynamic programming and game theory, asked in Amazon, Microsoft and Morgan Stanley interviews.

Coins of values arr[0], arr[1], …, arr[n - 1] lie in a row, where n is even. You and an opponent take turns, and you move first. On each turn a player removes either the leftmost or the rightmost remaining coin and keeps its value.

The opponent is just as clever as you: every choice they make is the one that is best for them.

Return the maximum total value you can guarantee to collect.

Example 1

Input
arr = [5,3,7,10]
Output
15
Explanation
Take 10; whichever end the opponent takes (5 or 7), you then take 5 — 10 + 5 = 15. Starting with 5 would let the opponent take 10.

Example 2

Input
arr = [8,15,3,7]
Output
22
Explanation
Take 7; the opponent takes 8 or 3, and you then take 15 — 7 + 15 = 22.

Example 3

Input
arr = [2,2]
Output
2

Constraints

  • 2 <= n <= 1000
  • n is even
  • 1 <= arr[i] <= 10^6
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number}
 */
var maximumAmount = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Optimal Strategy For A Game — Solution in Python, Java & C++

Optimal Strategy For A Game solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Optimal Strategy For A Game is a medium coding problem on arrays, dynamic programming and game theory, asked in Amazon, Microsoft and Morgan Stanley interviews.

Problem statement

Coins of values arr[0], arr[1], …, arr[n - 1] lie in a row, where n is even. You and an opponent take turns, and you move first. On each turn a player removes either the leftmost or the rightmost remaining coin and keeps its value.

The opponent is just as clever as you: every choice they make is the one that is best for them.

Return the maximum total value you can guarantee to collect.

Example 1

Input: arr = [5,3,7,10]
Output: 15
Explanation: Take 10; whichever end the opponent takes (5 or 7), you then take 5 — 10 + 5 = 15. Starting with 5 would let the opponent take 10.

Example 2

Input: arr = [8,15,3,7]
Output: 22
Explanation: Take 7; the opponent takes 8 or 3, and you then take 15 — 7 + 15 = 22.

Example 3

Input: arr = [2,2]
Output: 2

Constraints

  • 2 <= n <= 1000
  • n is even
  • 1 <= arr[i] <= 10^6

Hints for Optimal Strategy For A Game

  1. Hint 1

    Greedily taking the larger end coin fails: in [8,15,3,7], grabbing the 8 hands the 15 to the opponent.

  2. Hint 2

    After any sequence of moves, the coins left always form a contiguous block arr[i..j]. Define the best you can do on such a block when it is your turn.

  3. Hint 3

    Both players play optimally, so on a block the player to move collects sum(i..j) - (what the opponent collects on the block left after the move). That gives best[i][j] = sum(i..j) - min(best[i+1][j], best[i][j-1]).

How to solve Optimal Strategy For A Game

The game state is just the remaining block i..j and whose turn it is — and since both players reason identically, one function best[i][j] (the most the player to move can collect from i..j) describes both. The mover gets the whole block minus whatever the opponent manages to collect afterwards.

Approach

  1. Build prefix sums so sum(i..j) is O(1).
  2. For a single coin, best[i][i] = arr[i].
  3. For longer blocks (by increasing length): best[i][j] = sum(i..j) - min(best[i + 1][j], best[i][j - 1]) — take the end that leaves the opponent the smaller optimum.
  4. Return best[0][n - 1].

Why it works

The two players' totals on a block always add up to the block's sum. If the mover takes arr[i], the opponent becomes the mover on i+1..j and collects best[i+1][j], so the first player ends with sum(i..j) - best[i+1][j]; symmetrically for arr[j]. Maximising the mover's share is minimising what the opponent gets, which is exactly the recurrence. Induction on block length proves each best[i][j] optimal.

Complexity

  • Time — O(n^2)
  • Space — O(n^2) (or O(n) with a rolling row)

Pitfalls

  • Assuming the opponent plays greedily — they play optimally, which is what makes the min correct.
  • The classic formulation arr[i] + min(best[i+2][j], best[i+1][j-1]) is equivalent but easier to get wrong at the borders.
  • The total of all coins is at most 1000 * 10^6 = 10^9, which still fits in 32 bits.

Reference solution

Python

from typing import List

def maximumAmount(arr: List[int]) -> int:
    n = len(arr)
    pre = [0] * (n + 1)
    for i, v in enumerate(arr):
        pre[i + 1] = pre[i] + v
    best = arr[:]  # best[i] for the current length, block i..i+len-1
    for length in range(2, n + 1):
        nxt = [0] * (n - length + 1)
        for i in range(n - length + 1):
            j = i + length - 1
            nxt[i] = pre[j + 1] - pre[i] - min(best[i + 1], best[i])
        best = nxt
    return best[0]

Java

public static int maximumAmount(int[] arr) {
    int n = arr.length;
    long[] pre = new long[n + 1];
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + arr[i];
    long[] best = new long[n];
    for (int i = 0; i < n; i++) best[i] = arr[i];
    for (int len = 2; len <= n; len++) {
        for (int a = 0; a + len - 1 < n; a++) {
            int b = a + len - 1;
            best[a] = pre[b + 1] - pre[a] - Math.min(best[a + 1], best[a]);
        }
    }
    return (int) best[0];
}

C++

int maximumAmount(vector<int>& arr) {
    int n = arr.size();
    vector<long long> pre(n + 1, 0), best(arr.begin(), arr.end());
    for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + arr[i];
    for (int len = 2; len <= n; len++) {
        for (int a = 0; a + len - 1 < n; a++) {
            int b = a + len - 1;
            best[a] = pre[b + 1] - pre[a] - min(best[a + 1], best[a]);
        }
    }
    return (int) best[0];
}

JavaScript

var maximumAmount = function(arr) {
    var n = arr.length;
    var pre = [0];
    for (var i = 0; i < n; i++) pre.push(pre[i] + arr[i]);
    var best = arr.slice();
    for (var len = 2; len <= n; len++) {
        var next = [];
        for (var a = 0; a + len - 1 < n; a++) {
            var b = a + len - 1;
            next.push(pre[b + 1] - pre[a] - Math.min(best[a + 1], best[a]));
        }
        best = next;
    }
    return best[0];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming