题目描述

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

请从这 $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,10000]$ 范围内。

来源

回溯