538. Stone Game
A row of stone piles sits between two players. piles[i] is the number of stones in pile i. The row always has an even number of piles, and the total number of stones is odd, so a tie is impossible.
The players alternate turns. On each turn, the current player removes the entire pile at either end of the row and banks its stones. Both players play perfectly, each trying to end the game holding the larger total.
Your function receives the array piles and returns true if the player who moves first is guaranteed to win, and false otherwise.
Example 1:
Input: piles = [5, 3, 4, 5]
Output: true
Explanation: The first player opens with the leading 5. If the opponent grabs the closing 5, the first player takes the 4 for a total of 9 out of 17. If the opponent takes the 3 instead, the first player takes the closing 5 for 10 out of 17. Either way the first player passes half the stones.
Example 2:
Input: piles = [3, 8, 5, 1]
Output: true
Explanation: The odd-index piles hold 8 + 1 = 9 of the 17 stones. The first player can force themselves onto exactly those two piles: start by taking the 1, then always answer on the odd-index side. 9 > 8, so the first player wins.
Constraints:
- 2 ≤ piles.length ≤ 500
- piles.length is even
- 1 ≤ piles[i] ≤ 10⁵
- The total number of stones is odd, so someone always wins.
Hints:
Think in terms of subarrays: when it is your move on piles[i..j], define the best score difference (your stones minus your opponent's) you can force from here. Taking either end hands the opponent a smaller subarray of the same shape.
Now group the piles by index parity. There are equally many even-index and odd-index piles, and the two group sums cannot be equal (the total is odd). Can the first player always steer the game so they collect one entire parity group of their choosing?
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: piles = [5, 3, 4, 5]
Expected output: true