java - Taking turns picking endpoints, trying to get max -

say there array of integers. take turns person picking endpoints of array (either first or last element). objective implement algorithm find maximum score possible (always being first act).

example:

int[] arr = {3, 0, 4, 11, 1};  pick 3 arr = {0, 4, 11, 1}  opponent picks 0  arr = {4, 11, 1}  pick 4 arr = {11, 1}  opponent picks 1 arr = {11}  pick 11 arr = {}  maxpossible = 3 + 4 + 11 = 18 

i got recursive solution working, inefficient.

i want find dynamic programming solution (i new it).

any ideas?

here naive recursive implementation. believe it's o(2^n)

public int findbest(list<integer> a) {        return findbesthelper(a, 0, true); }  public int findbesthelper(list<integer> a, int score, boolean myturn) {      if(a.size() <= 0)         return score;      list<integer> removefirst = new arraylist<integer>(a);     removefirst.remove(0);      list<integer> removelast = new arraylist<integer>(a);     removelast.remove(removelast.size() - 1);      if(myturn)         return math.max(findbesthelper(removefirst, score + a.get(0), false), findbesthelper(removelast, score + a.get(a.size() - 1), false));     else         return math.max(findbesthelper(removefirst, score, true), findbesthelper(removelast, score, true));  } 

a trial example.

public void test()     {         int[] arr = {3, 0, 4, 11, 1};         int sum = 0;         int c1, c2, rs;         for(int i=0;i< arr.length/2; i++)         {          c1 =  arr[i]  ;          c2 = arr[arr.length - -1];          system.out.println("c1="+c1 + " - c2="+c2);            sum += (c1>c2) ?c1:c2;          }         if(arr.length%2 >0)         {          system.out.println("center="+arr[arr.length/2]);             sum += arr[arr.length/2];         }         system.out.println("sum="+sum );     }