题目描述

设有 $N$ 个正整数（$1 \le N \le 50$），每个数都大于等于 $1$ 且小于等于 $300$。

请从这 $N$ 个数中任取若干个数，要求不能取相邻的数，使得所取数字的和最大。

例如，当 $N=5$ 时，$5$ 个数分别为 $13,18,28,45,21$。可以有如下取法：

• 取 $13,28,21$，和为 $62$；
• 取 $13,45$，和为 $58$；
• 取 $18,45$，和为 $63$。

因此最大和为 $63$。

输入格式

第一行输入一个整数 $N$。

第二行输入 $N$ 个符合条件的整数。

输出格式

输出一个整数，表示最大和。

样例

5
13 18 28 45 21

63

数据范围

$1 \le N \le 50$，每个整数均在 $[1,300]$ 范围内。

来源

动态规划