題目描述

航天博物館中有一個(gè)互動(dòng)游戲。給出N個(gè)數(shù)字(C1、C2、C3、…、CN)排成一排，現(xiàn)有A和B兩個(gè)人輪流取數(shù)字，每次可以取當(dāng)前剩余數(shù)字中最左側(cè)或者最右側(cè)之一并拿走。最終每個(gè)人分?jǐn)?shù)是拿到的數(shù)字之和。分?jǐn)?shù)較高者將獲得航天紀(jì)念品一個(gè)。

游戲開(kāi)始時(shí)，A先取數(shù)字，兩人都會(huì)按照最優(yōu)策略來(lái)取數(shù)字，現(xiàn)在想知道A先手可以拿到最多的分?jǐn)?shù)是多少？

輸入說(shuō)明

第一行：?jiǎn)蝹€(gè)整數(shù)N，表示一共多少個(gè)數(shù)字，1≤N≤5000

第二行到第N+1行：第i+l行有一個(gè)整數(shù)Ci，1≤Ci≤5000

輸出說(shuō)明

一個(gè)整數(shù)，表示如果雙方都按最優(yōu)策略玩游戲，A先手可以得到的分?jǐn)?shù)。

輸入樣例?

4

30

25

10

35

輸出樣例

60

https://www.nowcoder.com/practice/19c98d950b3347d19f991d10bde12288

?？皖}目與省賽有一點(diǎn)區(qū)別。

?？皖}目答案及說(shuō)明：

??????????????????????????

省賽題目答案：