题目描述

给定 $n$ 个数字构成的序列 $a_1, a_2, a_3, \dots, a_n$，请从中挑选一些数字构成一个独立集。所谓独立集就是原数列的一部分数字，且这些数字在原数列中均不相邻。找出数字之和最大的独立集，输出这些数字的和。注意若数字都是负数，可以不挑任何数，此时输出 0。

输入格式

• 第一行：单个整数 $n$
• 第二行：$n$ 个整数 $a_1, a_2,\dots,a_n$

输出格式

• 单个整数：表示最大的独立集

5
10 20 30 -10 3

43

数据范围

• 对于 $30\%$ 的数据，$1\le n\le 20$；
• 对于 $60\%$ 的数据，$1\le n\le 3,000$；
• 对于 $100\%$ 的数据，$1\le n\le 100,000$；
• $-10000\leq a_i\le 10000$