出處https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1832
解題策略
記憶優化DP，列舉區間
假設輸入的n個元素儲存在x[1]到x[n]
dp(i,j)表示前手從第i個到第j個(包含第i個與第j個)能獲得的最大值，
因為每一次只能從左邊或右邊取至少一個以上，
若前手取第i+1到第j個，後手就是dp(i,i);若前手取第i+2到第j個，後手就是dp(i,i+1)，
以此類推，前手取第j到第j個，後手就是dp(i,j-1);
若前手取第i到第i個，後手就是dp(i+1,j);若前手取第i到第i+1個，後手就是dp(i+2,j)，
以此類推，前手取第i到第j-1個，後手就是dp(j,j);
若前手取第i到第j個，則後手為0。
為了讓前手取得最大，當然就是讓後手的所有可能性要取最小值，總和減去此最小值，就是先手的最大值
若i<j，dp(i,j)等於sum[i..j]-min(dp(i,i),dp(i,i+1),...,dp(i,j-1),dp(i+1,j),dp(i+2,j),...,dp(j,j),0)
否則i==j，d(i,i)為x[i]，因為至少要取一個
範例測資解析
4 -10 -20 7
先手A不能取7，因為後手B可以取4 -10，先手A只能取-20，先手A獲得-13，後手B獲得-6，-13-(-6)=-7
先手A取4，後手B取7，先手A取-10，後手取-20，先手A為-6，後手B為-13，-6-(-13)=7
參考程式碼