2001：链的独立集
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：普通裁判
命题人：
提交：3
解决：2
题目描述
给定 $n$ 个数字构成的序列 $a_1,a_2,...,a_n$，请从中挑选一些数字构成一个独立集。所谓独立集就是原数列的一部分数字，且这些数字在原数列中均不相邻。找出数字之和最大的独立集，输出这些数字的和。注意若数字都是负数，可以不挑任何数，此时输出 $0$
输入
第一行：单个整数 $n$
第二行：$n$ 个整数 $a_1,a_2,...,a_n$
$1\le n\le 10^5, -10000\le a_i\le 10000$
输出
单个整数：表示最大的独立集
样例输入-1 复制
5
10 20 30 -10 3样例输出-1 复制
43