330. Optimal Strategy for a Game

n coins with given values are arranged in a row. Two players alternately pick a coin from either end of the remaining row (the first player moves first), each keeping the value of every coin they pick, and both play optimally to maximize their own total. Find the maximum total value the first player can guarantee for themself.

Input: The first line contains an integer n. The second line contains n space-separated integers, the coin values in a row. Output: Print a single integer - the maximum total value the first player can guarantee.

1 <= n <= 1000

This is a classic example of MINIMAX-style reasoning applied via DP - recognizing that 'both players play optimally' means modeling the OPPONENT's optimal (adversarial, from your perspective) choice explicitly within your own recurrence, not just computing your own best-case scenario.

Two players alternately pick coins from either end of a row, both playing optimally - find the maximum the first player can guarantee. Brute force: Try every possible sequence of picks for both players directly - this branches combinatorially (2^n possible pick sequences), impractical without memoization. Optimised: The KEY insight is that after YOU pick an end, your OPPONENT plays OPTIMALLY too - meaning they'll leave YOU the WORSE of your two possible next choices, not the better one, since they're trying to maximize THEIR OWN total, not help you. This adversarial 'assume the opponent plays against you optimally' framing is what the min() inside the recurrence captures precisely.

Recursively compute, for the current remaining range of coins [i, j], the best total the current player can guarantee by trying both choices - take the leftmost coin and then let the opponent play optimally on [i+1, j], or take the rightmost coin and let the opponent play optimally on [i, j-1] - and picking whichever choice leaves the current player with more after accounting for what the opponent will optimally leave them with. This directly models the alternating optimal-play structure of the game, but without caching, the same [i, j] ranges get recomputed repeatedly across different recursive paths, causing exponential blowup. Time: O(2^n) Space: O(n)

Use the same recursive minimax logic as the brute force, but cache the result for every distinct range [i, j] the first time it is computed, so subsequent calls for the same range return instantly. This is correct because the optimal value for any range only ever depends on the two smaller sub-ranges obtained by removing an end, and there are only O(n^2) distinct ranges total, so memoizing collapses the exponential recursion tree down to one computation per range. Time: O(n^2) Space: O(n^2)

Fill the DP table iteratively by increasing subarray length rather than recursively: for length 1 ranges the answer is just the single coin's value, and for each larger length, dp[i][j] = max(coin[i] + min(dp[i+2][j], dp[i+1][j-1]), coin[j] + min(dp[i][j-2], dp[i+1][j-1])) (treating out-of-range sub-problems as 0). Since each length's row only ever depends on the two previous shorter-length rows, only those are kept in memory instead of the full 2D table. This computes exactly the same values as the memoized version but processes them in a controlled order that allows discarding older diagonals, cutting memory from quadratic down to linear. Time: O(n^2) Space: O(n)

1. dp[i][j] = the maximum value the player TO MOVE can guarantee from subarray arr[i..j], assuming both play optimally from here on. 2. Picking arr[i] leaves the OPPONENT facing arr[i+1..j] - whichever end they then pick, they leave YOU the WORSE of the two remaining sub-ranges for your next turn, so picking i is worth arr[i] + min(dp[i+2][j], dp[i+1][j-1]). 3. Picking arr[j] is symmetric; dp[i][j] = the MAX of these two picks, since the CURRENT player chooses whichever option is better for THEM.

Time: O(n²) - filling the interval DP table, one cell per (i,j) range. Space: O(n²), for the full DP table.

Test n = 1 (the first player simply takes the only coin) and n at its upper bound of 1000 for the O(n^2) DP.

Be ready to explain the min()-inside-max() structure clearly - it's easy to mistakenly think 'my next turn gets the better sub-range', but a truly optimal opponent will always leave you the WORSE one, which is exactly why min() appears nested inside the max() choice.