🎢平方峰过山车：平方峰上顶点单，指数飞升序列短

今天一早，村长的飞鸽传书就砸在我桌上——那个奇奇怪怪游乐园又来新活了。上次锯齿过山车的奖金还没结清呢，这次又搞了个什么姐妹项目——平方峰过山车！

“又是过山车？这游乐园是跟过山车杠上了还是预算只够建一种项目？” 我展开任务书，只见上面画着一张极其诡异的设计图——轨道中间高、两边低，还不是均匀分布的，像一座被镜子对折过的陡峭山峰！

“这爬坡方式也太反人类了吧！从起点开始，每次不是乘2，是平方！平方！x变成x²，再变成x⁴，一路指数爆炸往上飙，到了峰值再对称地开方降回来——起步是2G的推背感，到山顶直接变成256G，是要把乘客压成二维生物吗？！”

平方峰过山车设计规范：

• 从数组 nums 中选子集，使子集的元素能排成这样的对称模式：[x,x²,x⁴,...,x^k,...,x⁴,x²,x]
• 也就是说，先不断平方上升到顶，再对称下降
• 例如：[2, 4, 16, 4, 2] 、[3, 9, 3] 都符合；但 [2, 4, 8, 4, 2] 不符合（8 不是 4 的平方）
• 目标：找出能满足这个模式的最大子集的大小。

“这帮人是不是对‘刺激’有什么误解？”我忍不住吐槽，“重力加速度不够，用平方来凑？别的游乐园追求的是‘游客的欢笑’，他们追求的是‘游客的尖叫和扁平化’！”

但我目光下移，突然看到了村长在图纸最下方用红笔加粗的一行小字：

村长注：nums 长度最大 10^5，每个数最大 10^9。奖金翻倍！务必搞定！！

“奖金翻倍……”我盯着那四个字，原本吐槽的嘴瞬间闭上了。上次锯齿过山车的钱还没到账，这次翻倍——虽然不知道基数是多少，但翻倍这个词就像游戏里爆出双倍经验卡一样让人心跳加速。

我十指交叉，发出一声清脆的响声，脑子迅速活动起来——这模式有个致命的特点：序列关于正中心对称。

第一步：对称结构

对称意味着配对，配对意味着频次。序列里除了中心点可以独一份，其他所有值都必须成对出现。

也就是说，对于[x, x², x⁴, …, x^k, …, x⁴, x², x]，除了山顶那个峰值可以独一份，其他所有值都必须成对出现（左右各一个）。所以，答案一定是个奇数：峰值占一个，左右各一对占两个，像一座完美的山峰。

结构搞清楚了。那直接暴力枚举每个数作为起点，不断平方往上找，统计最长合法序列，可行吗？

问题是：枚举每个数作为起点的时候，这个序列会往上爬多高？

第二步：平方增长是最强剪刀

我盯着那个“平方”操作——平方增长是什么概念？2 平方变 4，4 平方变 16，16 平方变 256，256 平方变 65536，65536 平方直接炸穿 10^9。从最小的 2 开始，平方五次就超过任务给出的数值上限了。也就是说，序列的长度绝对不会超过 2×5+1=11——才十一个元素！

这意味着暴力枚举每个不同的数作为起点时，最多只需要尝试 5-6 次平方操作！总计算量完全可控。平方增长简直就是最强的剪刀，一刀把指数级可能性砍成了常数级。

“先搞个哈希表统计每个数字出现的次数。”我掏出键盘，“然后对每个数字进行’攀登’，取最大的序列长度！”

第三步：特判 1

等等——手指悬在键盘上，一个极其特殊的数字从脑子里蹦了出来： 1！——1 的平方永远是 1，如果把它当成普通数字处理，平方操作会陷入死循环！

1 必须单独处理，不能进入循环。序列里可以塞任意多个 1，但任务要求选子集，1 的个数受限于数组里实际出现了多少个 1。如果数组里有 5 个 1，最多取 5 个排成 [1,1,1,1,1]；如果有 4 个 1，最多取 3 个——因为中心点要独一份，两侧必须对称。所以，1 的答案就是：奇数直接取，偶数减一。

搞定 1 这个特例，把它从哈希表里踢出去，防止后续循环踩坑。

第四步：暴力枚举

剩下的逻辑就清晰了：枚举每个不同的数作为起点 x，尝试不断平方，看能爬多高。

from collections import Counter

class Solution:
    def maximumLength(self, nums: list[int]) -> int:
        cnt = Counter(nums)
        
        # 特判 1：1的平方还是1，只能取奇数个
        ans = (cnt[1] - 1) | 1  # 偶数减一，奇数不变
        del cnt[1]  # 处理完1，踢出去，防止死循环
        
        for num in set(nums):
            if num == 1:
                continue  # 1 已经处理过了
            
            res = 0
            temp = num
            # 只要当前数至少有2个，就可以左右各放一个
            while cnt.get(temp, 0) >= 2:
                res += 2  # 左右各一个，+2
                temp *= temp  # 平方，继续上升
            
            # 退出循环时，检查顶点是否存在
            ans = max(ans, res + (1 if cnt.get(temp, 0) >= 1 else -1))
        
        return ans

O(n) 统计频次，O(n · log log M) 暴力扩展——M 是最大值 10^9，最大序列长度不超过 11，总复杂度约等于 O(n)，干净利落。

村长拿着结果，乐颠颠地往游乐园方向跑了，说这次要是能把锯齿过山车的尾款和平方峰的翻倍奖金一起讨回来——他就给那台二手服务器换个静音风扇。看着老头的背影消失在村口，我忍不住开始好奇这个游乐园的策划到底是什么来头。

锯齿过山车好歹还是线性增长，相邻节点差不超过1，轨道起伏有规律可循；到了平方峰，直接放飞自我，起步就是平方，指数爆炸往上飙，到了峰值再开方降回来。这脑回路，策划怕不是从数学系毕业的——乘客不在他们的考量范围内，他们在乎的是“这个递推式够不够漂亮”。

平方峰上顶点单，指数飞升序列短。 数字一哥提前踢，暴力枚举直通关。

本作品采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。