楼上的谢了,根据你的思路写了一个,答案是对了,但是超时了........

算法的时间复杂度是O(n^2),应该可以过的饿.......

我用了递归~~~可能没完全理解你的意思,~~~最好帮偶把关键代码写一下,全代码就更感谢了,我的代码偶放一下先:
#include<stdio.h>
int p(int x[],int q,int k){
int s,d,t;
if(k==2)return x[q]>x[q+1]?(x[q]-x[q+1]):(x[q+1]-x[q]);
t=p(x,q+1,k-2);
if(x[q+1]>x[k-q-1])s=x[q]-x[q+1]+p(x,q+2,k-2);
else s=x[q]-x[k-q-1]+t;
if(x[q]>x[k-q-2])d=x[k-q-1]-x[q]+t;
else d=x[k-q-1]-x[k-q-2]+p(x,q,k-2);
return d>s?d:s;
}
int main(){
int n;
int a[1000];
int s,j=0;
while(scanf("%d",&n)!=EOF){
if(!n)break;
j++;
for(int i=0;i<n;i++)scanf("%d",&a[i]);
s=p(a,0,n);
printf("In game %d, the greedy strategy might lose by as many as %d points.\n",j,s);
}
}

哈.原来是这样.递归肯定超时,要么用记忆化搜索,要么递推实现,代码很短的.
偶的代码:
[CODE]for(i=1;i<=n;i++)
{
scanf("%d",a+i);
f[i][i]=-a[i];
}
for(k=1;k<=n;k++)
for(i=1;k+i<=n;i++)
{
j=i+k;
if((j-i)%2)
f[i][j]=f[i][j-1]+a[j]>f[i+1][j]+a[i]?f[i][j-1]+a[j]:f[i+1][j]+a[i];
else
a[i]>=a[j]?f[i][j]=f[i+1][j]-a[i]:f[i][j]=f[i][j-1]-a[j];
}[/CODE]