# UVa 10891

## Summary

This is a variation of a classic Dynamic Programming problem, only in this one, you can take any number of numbers from either end.

## Explanation

In the classic problem, the recurrence is:

${\displaystyle best(i,j)=\max(value(i)-best(i+1,j),value(j)-best(i,j-1)}$

Now we just add an iteration over it:

${\displaystyle best(i,j)=\max _{k=0,\ldots ,j-i}(\max(values(i,i+k)-best(i+k,j),values(j-k,j)-best(i,j-k))}$

And the corresponding recursive memoization is trivial to implement.

4
4 -10 -20 7
4
1 2 3 4
6
1 1 1 1 1 1
5
-1 0 0 0 5

7
10
6
6