Here's the simplified problem statement:

Given an array -> [2,3,1,4,9]. You can choose either element from beginning or end of the array. Keep choosing until you've chosen N/2 elements( where N is array size ).

Find the maximum sum of N/2 elements chosen this way.

Ex: [2,3,1,4,1,9]
Result: 2 + 9 + 3 = 14

Note: Greedy solutions won't work. For ex: [2,3,1,4,9,1] -> Result : 4 + 9 + 1 = 14

Here's the rough idea I had discussed during interview:

solve(start, end) = max( arr[start] + solve(start+1, end), arr[end] + solve(start, end-1) );

keep a counter during the recursive calls and stop when count is N/2

To optimize the solution: you can cache the results.