825. Ends Game Margin
Two traders split a line of crates holding piles[i] coins in crate i (a crate may hold a negative amount: a debt). They alternate turns and you move first. On a turn the player must take either the leftmost or the rightmost remaining crate and add its value to their own score. The game ends when no crates remain.
Both players play perfectly, each trying to maximise their own score minus the other's. Return the final value of your score - opponent score; it may be negative.
Aim for time O(n^2) and extra space O(n).
Example 1
- Input:
- piles = [6,2,9,4]
- Output:
- 9
- Explanation:
Take 6, the opponent takes 4, you take 9 and they take 2: you score 15 against 6, a margin of 9 - and no line of play does better.
Example 2
- Input:
- piles = [5,12,3]
- Output:
- -4
- Explanation:
Whichever end you take, the opponent then takes the 12: you finish with 8 against 12, a margin of -4.
Constraints
1 ≤ piles.length ≤ 1000
-1000 ≤ piles[i] ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n^2)
- Space
- O(n)