#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>using namespace std;int d[1001][1001],num[1001];int bfs(int x,int y){ if(d[x][y]!=-1) return d[x][y]; if(y-x==1) return d[x][y]=abs(num[x]-num[y]); int t,tt; if(num[x+1]>=num[y]) t=bfs(x+2,y)+num[x]-num[x+1]; else t=bfs(x+1,y-1)+num[x]-num[y]; if(num[x]>=num[y-1]) tt=bfs(x+1,y-1)+num[y]-num[x]; else tt=bfs(x,y-2)+num[y]-num[y-1]; d[x][y]=max(t,tt); return d[x][y];}int main(){ int n,cas=1; while(scanf("%d",&n)!=EOF) { if(n==0) break; memset(d,-1,sizeof(d)); for(int i=1; i<=n; i++) { scanf("%d",&num[i]); } int t=bfs(1,n); printf("In game %d, the greedy strategy might lose by as many as %d points.n",cas++,t); } return 0;}
