卡牌游戏_牛客题霸

旺仔哥哥某天想到了一个卡牌游戏，游戏规则如下：初始时，旺仔哥哥手中有张卡牌，自左向右排成一行，第张卡牌的分值为；每次操作，旺仔哥哥可以选取位于序列最左端的连续若干张卡牌（不少于张），并将它们替换为一张新卡牌；新卡牌被放入序列最左端，其分值等于本次被替换卡牌分值之和；游戏开始时旺仔哥哥的总分为。每完成一次替换操作，新卡牌的分值会累加到总分中；旺仔哥哥可以随时宣布游戏结束。

输入描述:

第一行输入一个整数 ，表示卡牌数量； 第二行输入 个整数 ，依次表示每张卡牌的分值。

输出描述:

输出一行一个整数，代表在最优策略下旺仔哥哥能够获得的最高总分。

示例1

输入

3
2 -1 2

输出

说明

在该样例中： 
 选择最左侧两张卡牌，分值之和为 ，总分累加为 ，新序列为 ； 
 再选择当前全部两张卡牌，分值之和为 ，总分累加为 ，最终总分为 ，序列长度变为 ，游戏结束。

示例2

输入

7
-4 3 0 7 -3 -5 -3

输出

说明

最优策略为，首先选择最左侧的四张卡牌，总分增加 。此时旺仔哥哥选择的四张卡牌被替换为一张分值为6 的卡牌，且被放入序列最左侧，此时自左向右卡牌的分值为 。

再选择最左侧的两张卡牌，总分增加 ，总分为 。此时旺仔哥哥选择的两张卡牌被替换为一张分值为  的卡牌，且被放入序列最左侧，此时自左向右卡牌的分值为 。

此时无论如何操作均无法使总分继续增大，旺仔哥哥选择结束游戏。