# 相反数转圈圈## 题目描述考试结束了这次的考试成绩很集中小A他想在这么多成绩种选出若干个数排成一个圈记为 $x_1x_2cdotsx_p$$p$ 为数的个数$x_1$和$x_p$相邻。小A定义一个圈为相反数圈当且仅当这个圈满足以下条件：- $p ge 2$。- 令 $y_i = x_i + 1 - x_i$$y_p=x_1-x_p$如果把 $y_1$ 到 $y_p$ 按 $y_1y_2cdot - 科技

解题思路

首先我们可以观察到，对于一个合法的相反数圈，它的长度 $p$ 必须是偶数，因为 $y_1$ 和 $y_p$ 是相反数，而相反数的个数也必须是偶数。

我们可以把这个相反数圈看作一个环形链表，每个节点都有一个值和一个指针指向下一个节点。我们可以用哈希表来存储每个值对应的节点，方便我们查找。

我们首先遍历输入的数列，将每个数出现的次数存入哈希表，并记录出现次数最多的数的个数。

接下来，我们从哈希表中取出一个数 $x$，查找它的相反数是否存在。如果存在，我们就可以将它和相反数构成一个相反数圈的一部分。我们将这个数和它的相反数从哈希表中删除，并将它们的出现次数都减1。我们继续查找下一个数，直到没有数可以构成相反数圈为止。

在构成相反数圈的过程中，我们可以计算出这个相反数圈中所有数的和，并更新最大和。

最后，我们还需要考虑可能存在单个数的情况。如果哈希表中还有剩余的数，我们可以将这些数两两配对，构成一个长度为2的相反数圈。如果剩下的数的个数是偶数，那么所有数都可以配对，否则，我们需要找到剩下数中出现次数最多的数，将它和它的相反数配对。这样，我们就可以得到一个额外的相反数圈，它只有一个数。

最后，我们将所有相反数圈的和加起来，就得到了最终的答案。

算法步骤

创建一个哈希表，用于存储每个数对应的节点和出现次数。
遍历输入的数列，将每个数出现的次数存入哈希表，并记录出现次数最多的数的个数。
初始化最大和为0。
从哈希表中取出一个数 $x$，查找它的相反数是否存在。
- 如果存在，将它和相反数构成一个相反数圈的一部分。
- 将这个数和它的相反数从哈希表中删除，并将它们的出现次数都减1。
- 计算相反数圈中所有数的和，并更新最大和。
- 继续查找下一个数。
- 如果没有数可以构成相反数圈，转到步骤5。
如果哈希表中还有剩余的数，将这些数两两配对，构成一个长度为2的相反数圈。
- 如果剩下的数的个数是偶数，所有数都可以配对。
- 如果剩下的数的个数是奇数，找到剩下数中出现次数最多的数，将它和它的相反数配对。
- 计算相反数圈中所有数的和，并更新最大和。
返回最大和作为答案。

复杂度分析

假设输入的数列长度为 $n$。

空间复杂度为 $O(n)$，主要用于存储哈希表和相反数圈。