Optimal Strategy for a Game
You are given an array arr of positive integers. Two players take turns picking numbers, with Player 1 going first.
On each turn, a player picks either the first or the last element of the remaining array. The player adds the picked number to their score. The game ends when the array is empty.
Assuming both players play optimally to maximize their own score, return the maximum score Player 1 can achieve.
Examples
Input: [5,3,7,10]
Output: 15
Input: [8,15,3,7]
Output: 22
Hints
Use interval DP. Define `dp[l][r]` as the maximum score the current player can achieve from subarray `arr[l..r]`.
The total sum of `arr[l..r]` is fixed. If a player takes `arr[l]`, the opponent gets `dp[l+1][r]` from the remainder. So `dp[l][r] = max(arr[l] + (sum[l+1..r] - dp[l+1][r]), arr[r] + (sum[l..r-1] - dp[l][r-1]))`.
Equivalently, `dp[l][r] = max(sum[l..r] - dp[l+1][r], sum[l..r] - dp[l][r-1])`. Precompute prefix sums for O(1) range sum queries.
Related Problems
Optimal Strategy for a Game
You are given an array `arr` of positive integers. Two players take turns picking numbers, with Player 1 going first.