Two players take turns taking a stone pile from either end of an array and both play optimally. Determine whether the first player can finish with more stones.
Stone Game
You are given an even-length array of positive integers piles, where piles[i] is the number of stones in the i-th pile.
Two players, Alex and Lee, play a game. They take turns, with Alex moving first. On each turn, a player must remove exactly one pile from either the left end or the right end of the remaining row of piles. The stones from the chosen pile are added to that player's total.
Both players play optimally.
Return whether Alex can end the game with a strictly larger total than Lee.
Goal
Decide if the first player can force a win under optimal play.
Input Format
Input
- An integer array
pilesof even length.
Interpretation
piles[i]is the number of stones in pilei.- Each move removes one pile from either the leftmost or rightmost remaining position.
Output Format
Output
- Return
trueif Alex can collect more stones than Lee with optimal play. - Otherwise, return
false.
Constraints
2 <= piles.lengthpiles.lengthis even1 <= piles[i]- All players play optimally
Example 1
Input
piles = [5,3,4,5]
Output
true
Explanation
Alex can take 5 from the right, then no matter what Lee does, Alex can secure a higher final total.
Example 2
Input
piles = [3,7,2,3]
Output
true
Explanation
With optimal play, Alex can force a win by choosing ends that preserve a larger eventual total.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.