1 //J. Boxes Game-取数博弈-不会，套的板子

 2 #include<iostream>

 3 #include<algorithm>

 4 #include<cstdio>

 5 #include<cstring>

 6 #include<cmath>

 7 using namespace std;

 8 const int maxn=1e3+10;

 9 int nums[maxn];

10 int dp[maxn][maxn];

11 int main()

12 {

13     int t,n;

14     scanf("%d",&t);

15     while(t--){

16         cin>>n;

17         int sum=0;

18         memset(nums,0,sizeof(nums));

19         memset(dp,0,sizeof(dp));

20         for(int i=0;i<n;++i)

21         {

22             cin>>nums[i];

23             sum+=nums[i];

24         }

25         int len=0;

26         //分n为奇偶分类讨论下初始情况，len是区间[st,en]的长度-1

27         if(n%2==1)

28         {

29             for(int i=0;i<n;++i)

30                 dp[i][i]=nums[i];

31             len = 2; //倒数下一轮的区间长度

32         }

33         else

34         {

35             for(int i=0;i<n-1;++i)

36             {

37                 dp[i][i+1] = max(nums[i],nums[i+1])-min(nums[i],nums[i+1]);

38             }

39             len =3;

40         }

41         while(len<n)

42         {

43             for(int i=0;i+len<n;++i)

44             {

45                 dp[i][i+len]=max(min(nums[i]-nums[i+1]+dp[i+2][i+len],nums[i]-nums[i+len]+dp[i+1][i+len-1]),

46                     min(nums[i+len]-nums[i+len-1]+dp[i][i+len-2],nums[i+len]-nums[i]+dp[i+1][i+len-1]));

47             }

48             len+=2;

49         }

50         cout<<(sum+dp[0][n-1])/2-(sum-dp[0][n-1])/2<<endl;

51     }

52     return 0;

53 }