Description
Alice and Bob play a game removing stones from ends of a row. Score is sum of remaining stones. Alice goes first. Return Alice's score - Bob's score with optimal play.
Examples
Input:
stones = [5,3,1,4,2]Output:
6Explanation:
Max difference.
Input:
stones = [1]Output:
1Explanation:
Edge case with a single-element array.
Input:
stones = [7,90,5,1,100,10,10,2]Output:
122Explanation:
Alice and Bob play optimally to maximize their own score minus opponent's score. Alice starts and can remove either 7 (leftmost) or 2 (rightmost). The key insight is that when you remove a stone, your score increases by the sum of all remaining stones. Through optimal play, Alice can achieve a score difference of 122 by strategically choosing which ends to remove from.
Constraints
- •
2 ≤ stones.length ≤ 1000