Optimal Candy Collection

In this problem, you are given a sequence of integers representing the number of candies in boxes arranged in a row. Two players, Tom (the first player) and Jerry (the second player), take turns selecting a box from either end of the row. Both players play optimally. Your task is to determine the maximum number of candies that Tom can collect.

The game is defined by the recurrence relation in the dynamic programming solution: \[ \text{dp}[i][j] = \max\Big( candies[i] + \min(\text{dp}[i+2][j],\, \text{dp}[i+1][j-1]),\; candies[j] + \min(\text{dp}[i+1][j-1],\, \text{dp}[i][j-2]) \Big) \] where \( dp[i][j] \) represents the maximum candies Tom can secure from the subarray of candies starting at index \( i \) and ending at index \( j \).

inputFormat

The first line of input contains a single integer \( n \) (the number of candy boxes). The second line contains \( n \) space-separated integers, where each integer represents the number of candies in a box.

outputFormat

Output a single integer representing the maximum number of candies that Tom can collect if both players play optimally.

4
1 2 9 4

10