消消乐
EXY-PG-0230
题目描述
给定一个由 $n$ 个整数构成的数组 $a=[a_{1},…,a_{n}]$。每次你可以对数组 $a$ 进行以下操作，直到数组 $a$ 变为空：
- 指定 $a$ 中的一个元素，获得该元素两侧相邻元素之和的分数，并将该元素从 $a$ 中删去。
特别地，如果相邻元素不存在则该元素的值视为 0。例如，对于 $a=[1,2,3]$ 可以进行以下操作：
- 指定元素 2，获得分数 1+3，删去 2 后 $a=[1,3]$；
- 指定元素 1，获得分数 0+3，删去 1 后 $a=[3]$；
- 指定元素 3，获得分数 0+0，删去 3 后 $a$ 变为空。
请问你能获得的分数总和最大是多少？
输入格式
第一行，一个正整数 $n$，表示数组长度。
第二行，$n$ 个非负整数 $a_{1},…,a_{n}$，表示数组 $a$ 中的整数。
输出格式
输出一行，一个整数，表示能获得的最大分数总和。
样例说明
样例 1
输入：
6
1 6 3 2 9 1
输出：
55样例 2
输入：
5
3 1415 926 53 58
输出：
5771数据范围
对于 40% 的测试点，保证 $1≤n≤50$，$0≤a_{i}≤10^{3}$。
对于所有测试点，保证 $1≤n≤100$，$0≤a_{i}≤10^{9}$。