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.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Game Theory
- Asked at: Amazon, Microsoft, Morgan Stanley
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 1000n is even1 <= arr[i] <= 10^6
Hints for Optimal Strategy For A Game
Hint 1
Greedily taking the larger end coin fails: in
[8,15,3,7], grabbing the 8 hands the 15 to the opponent.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.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 givesbest[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
- Build prefix sums so
sum(i..j)isO(1). - For a single coin,
best[i][i] = arr[i]. - 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. - 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
mincorrect. - 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