TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

40.0% (2/5)

Tags

Description

這是普遜。

這是李胖。

眾所皆知,普遜跟李胖都很愛吃,也很愛玩以「吃」當主題的遊戲。
現在地上排了$N$碗麵,標號$0\text{~}N-1$,每碗麵都有它的飽足感$A_i$,普遜跟李胖每次都能從「最左邊」或「最右邊」拿「任意碗數」的麵,他們都希望最後能吃到最飽,所以每次都會對他們採取最好的策略,而所謂吃得多飽就是吃到的麵的飽足感總和。

遊戲由普遜先手,普遜想要知道他最多能多比李胖飽多少。

Input Format

輸入第一行包含正整數$N$,代表地面上有$N$碗麵。
接著第二行包含$N$個整數,$A_0\text{~}A_{N-1}$,其中$A_i$代表第$i$個罐頭的飽足感。

Output Format

輸出包含一個整數,代表在雙方皆採取最好的策略下,先手的普遜最多能比後手的李胖得到多少飽足感。

Sample Input

4
4 -10 -20 7

Sample Output

7

Hints

For $5\%$ of the testdata: $N\le 10$
For $20\%$ of the testdata: $N\le 50$
For $70\%$ of the testdata: $N\le 100$
For $100\%$ of the testdata: $N\le 1000$
For $100\%$ of the testdata: $\forall 0\le i<N,-10000\le A_i<10000$

Problem Source

UVa
Set by waynetu

Subtasks

For Testdata: 0 ~ 3, Score: 5
For Testdata: 4 ~ 7, Score: 15
For Testdata: 8 ~ 11, Score: 50
For Testdata: 12 ~ 17, Score: 30
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536
7 1000 65536 65536
8 1000 65536 65536
9 1000 65536 65536
10 1000 65536 65536
11 1000 65536 65536
12 1000 65536 65536
13 1000 65536 65536
14 1000 65536 65536
15 1000 65536 65536
16 1000 65536 65536
17 1000 65536 65536