A road named NoNameUno

Assume two pick pocketers  A, and B,  are settling on their end of the day earnings. The rule is that they will put all their picks on to a table. Then they will pick one coin at a time from either end of the line ( the coins are put on a line). Further assume that the number of coins is even, so both of them can have same number of coins. Fair game, as opposed to lot of things in life :-)

How should they go about picking in tern from either end of line to maxmize gain?

Example worth 1000 brainstorm !

S = { 6, 9, 1, 2, 16, 8 }. 

Greedy approach: Both A, and B will pick the larger of the coins at two ends.

A -> 8, B-> ... complete the process and see if A wins or B. You will see even though A has the first shot at it, A will loose. So greedy approach does not work. So what should be the strategy ? -- Think ...

The approach should be to minimize opponents next gain, rather than maximize your own gain. What an envy ! First approach is called Greedy, and the second approach is Strategy.

So at each turn, one would look at the difference between 2 left end coins and 2 right end coins and maximize the difference. In other words, you pick the greater difference.  

Look at Max {  ( a[i] - a[i+1] ),  ( a[N] - A[N-1] ) },   then pick either A[i] or A[N]

Time to find a functional equation !