该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定 n 个数字构成的序列 a1,a2,a3,…,an，请从中挑选一些数字构成一个独立集。所谓独立集就是原数列的一部分数字，且这些数字在原数列中均不相邻。找出数字之和最大的独立集，输出这些数字的和。

注意空集也是独立集，其元素之和定义为 0。

输入格式

第一行：单个整数 n

第二行：n 个整数a1,a2,…,an

输出格式

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

5
10 20 30 -10 3

43

数据规模与约定

对于 30% 的数据，1≤n≤20；

对于 60% 的数据，1≤n≤3,000；

对于 100% 的数据，1≤n≤100,000；

−10000≤ai≤10000