3142: 圆环独立集（一）
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
给定一个长度为 �n 的环状数列 �1,�2,⋯,��a1,a2,⋯,an，请从中间挑选出一些数字组成一个独立集，使得该独立集中的数字之和达到最大。
所谓环状，是指在考虑相邻关系时，需要把 �1a1 和 ��an 也看做是一对邻居。所谓独立集，就是挑选出的数字在原来的圆环上不能相邻。
输入
- 第一行：单个整数表示 �n。
- 第二行：�n 个整数表示 �1,�2,⋯,��a1,a2,⋯,an。
- 对于 30%30% 的数据，1≤�≤201≤n≤20；
- 对于 60%60% 的数据，1≤�≤50001≤n≤5000；
- 对于 100%100% 的数据，1≤�≤500,0001≤n≤500,000，
- 1≤��≤1,000,0001≤ai≤1,000,000。
输出
- 单个整数：表示独立集的数字之和的最大值。
样例输入 复制
5
1 1 1 1 1样例输出 复制
2提示
这个例子告诉我们最优独立集不一定是最大独立集