Maximum sum in array with special conditions

Question

Assume we have an array with n Elements ( n%3 = 0).In each step, a number is taken from the array. Either you take the leftmost or the rightmost one. If you choose the left one, this element is added to the sum and the two right numbers are removed and vice versa.

Example: A = [100,4,2,150,1,1], sum = 0.

1. take the leftmost element. A = [4,2,150] sum = 0+100 =100

2.take the rightmost element. A = [] sum = 100+150 = 250

So the result for A should be 250 and the sequence would be Left, Right.

How can I calculate the maximum sum I can get in an array? And how can I determine the sequence in which I have to extract the elements?

I guess this problem can best be solved with dynamic programming and the concrete sequence can then be determined by backtracking.

Answer 1

The underlying problem can be solved via dynamic programming as follows. The state space can be defined by letting

M(i,j) := maximum value attainable by chosing from the subarray of
          A starting at index i and ending at index j
          for any i, j in {1, N} where `N` is the number of elements
          in the input.

where the recurrence relation is as follows.

M(i,j) = max { M(i+1, j-2) + A[i], M(i+2, j-1) + A[j] }

Here, the first value corresponds to the choice of adding the beginning of the array while the second value connesponds to the choice of subtracting the end of the array. The base cases are the states of value 0 where i=j.