End-Removal Game Maximizing Score Difference
Two players alternately remove an item from either end of a row. The score for a removal equals the sum of the values still remaining afterward. Both play optimally; report the final score difference the first player secures.
Problem
Given an integer array values, players alternate turns (first player starts). On a turn a player removes either the leftmost or rightmost value; they gain points equal to the sum of the remaining values. Both maximize their own total. Return the maximum difference (first player score minus second player score) under optimal play.
Input
An integer array values.
Output
An integer: the optimal score difference for the first player.
Constraints
- 2 <= values.length <= 1000
- 1 <= values[i] <= 1000
Examples
Example 1
Input
values = [5,3,1,4,2]
Output
6
Optimal end removals leave the first player ahead by 6.
Example 2
Input
values = [7,90,5,1,100,10,10,2]
Output
122
The optimal difference under perfect play is 122.