Optimal Strategy for a Game
MediumP3Coding
Two players play on an array of positive integers. They alternate turns, and on each turn the player removes either the leftmost or the rightmost remaining number and adds it to their score. You move first. Both players play optimally, each trying to maximise their own final score.
Return [yourScore, opponentScore]. The two scores always add up to the sum of the array.
Example 1
- Input
- arr = [8,15,3,7]
- Output
- [22,11]
- Why
- Take 7, the opponent takes 8, you take 15, the opponent takes 3: 22 against 11.
Example 2
- Input
- arr = [2,2,2,2]
- Output
- [4,4]
Example 3
- Input
- arr = [5]
- Output
- [5,0]
Constraints
- 1 <= arr.length <= 1000
- 1 <= arr[i] <= 10^6
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 11. ⌘Enter runs, ⌘⇧Enter submits.