分数: 800 点
问题陈述
N 单元格排列成一行。 单元格已编号 1 通过 N 从左到右。
最初,所有单元格都是空的。 您可以以任意顺序执行任意次数的以下两种类型的操作:
- 选择三个 连续 清空单元格,并在三个单元格中各放一枚硬币。
- 选择三个 连续 装有硬币的单元格,然后移除所选单元格上的所有三个硬币。
执行完操作后,如果 i-第一个单元格包含一枚硬币,你得到 a_i 点。 您的分数是您从带有硬币的单元格中获得的所有分数的总和。
计算您可以获得的最高可能分数。
约束
- 3 \leq N \leq 500
- -100 \leq a_i \leq 100
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N a_1 a_2 : a_N
输出
打印答案。
示例输入 1
4 1 2 3 4
示例输出 1
9
我们将带有硬币的单元格表示为 o 和一个没有硬币的电池 . (一个点)。
一种最佳方式如下:
.... \rightarrow .ooo
我们得到 2 + 3 + 4 = 9 指的是这个方向。
示例输入 2
6 3 -2 -1 0 -1 4
示例输出 2
6
一种最佳方式如下:
...... \rightarrow ooo... \rightarrow oooooo \rightarrow o...oo
我们得到 3 + (-1) + 4 = 6 指的是这个方向。
示例输入 3
10 -84 -60 -41 -100 8 -8 -52 -62 -61 -76
示例输出 3
0