#N. 环上最大独立集

Type: RemoteJudge

1000ms

256MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给出一个有 $n$ 个点的环，每个点有点权 $a_i$ ，求满足点集内任何两个点在环上不相邻，且点权和最大的点集的点权和。注意点 $1$ 和点 $n$ 是相邻的。

第一行输入一个正整数 $n$ ，表示点的数目。第二行输入 $n$ 个以空格隔开的整数，依次表示各个点的点权 $a_i$ 。

输出一行一个整数，表示求得的最大点权和。

7
2 -2 8 6 -1 -5 5

对于 $50\%$ 的数据满足 $n\le 18$ ；对于 $100\%$ 的数据满足 $2\le n\le 10^5,|a_i|\le 10^9$ 。