basic optimal game stratgy

#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef long int li;

#define test()    int test_case;cin>>test_case;while(test_case--)
#define fr(i,n) for(int i=0;i<n;i++)
#define frr(i,a,n) for(int i=a;i<n;i++)
#define sll(a) scanf("%lld",&a)
#define sl(a) scanf("%ld",&a)
#define si(a) scanf("%i",&a)
#define sd(a)  scanf("%ld",&a)
#define sf(a) scanf("%f",&a)
#define rn(a) return a
#define pai pair<int,int>
#define pal pair<li,li>
#define pall pair<lli,lli>
#define ff first
#define ss second
#define mod  1000000007
#define mp make_pair
#define pb push_back
#define pll(a) printf("%lld\n",a);
#define pl(a) printf("%lld\n",a);
#define pi(a) printf("%d\n",a);
#define pd(a) printf("%lf\n",a);
#define pf(a) printf("%f\n",a);
lli  dp[3000][3000];
int solve(lli  arr[],int start,int end)
 {
   if(start>end)return 0;
  if(dp[start][end]!=-1)
{

return dp[start][end];
 }
  else if(start==end)
  {
 
  return dp[start][start];
 
 }
 else if(start+1==end)
  {


  return max(arr[start],arr[start+1]);
 
  }
//  else if(dp[start][end]!=-1) return dp[start][end];
  else
  {
 
  lli val1=arr[start]+min(solve(arr,start+2,end),solve(arr,start+1,end-1));
  lli  val2=arr[end]+min(solve(arr,start,end-2),solve(arr,start+1,end-1));
 
  dp[start][end]=max(val1,val2);
  }
return dp[start][end];
 }
int main()
{

int n;
lli arr[10000];
int t=1;
while(1)
 {
   cin>>n;
  lli  tot_sum=0;
    if(n==0) return 0;
   
   
    else
    {
    for(int i=0;i<n;i++)
{
cin>>arr[i];
    tot_sum+=arr[i];
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
dp[i][j]=-1;
}
for(int i=0;i<n;i++) dp[i][i]=arr[i];

solve(arr,0,n-1);
 cout<<dp[0][n-1]<<endl;
}
}