solution - Google Interview Question - 16th Feb 2011

O(n^2) solution:
f[i][j] = sum[i][j] + max(a[i]-f[i+1][j],a[j]-f[i][j-1])
f[i][i] = a[i];


#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
#define MAXPOT 1000
int optA[MAXPOT*MAXPOT];
int flag[MAXPOT*MAXPOT];
int optimal_a(int* coin,int first,int last,int numPots)
{
    if(flag[first * numPots + last] == 1)
    {
          return optA[first * numPots + last];
    }
    if(first == last)
    {
             optA[first * numPots + last] = coin[first];
             flag[first * numPots + last] = 1;
             return coin[first];
    }
    if(last < first)return 0;
    int val1,val2;
    val1= coin[first] - optimal_a(coin,first+1,last,numPots);
    val2= coin[last] - optimal_a(coin,first,last-1,numPots);
    return max(val1,val2);
}
int main()
{
    int numPots;
    cin>>numPots;
    int coin[numPots];
    memset((void*)flag,0,MAXPOT*MAXPOT*sizeof(int));
    for(int i = 0 ;i<numPots;i++)
            cin>>coin[i];
    cout<<optimal_a(coin,0,numPots-1,numPots)<<endl;
           
    return 0;
}