完全子集的最大元素和

难度: Hard

给你一个下标从 1 开始、由 n 个整数组成的数组。

如果一组数字中每对元素的乘积都是一个完全平方数，则称这组数字是一个 完全集 。

下标集 {1, 2, ..., n} 的子集可以表示为 {i₁, i₂, ..., i_k}，我们定义对应该子集的 元素和 为 nums[i₁] + nums[i₂] + ... + nums[i_k] 。

返回下标集 {1, 2, ..., n} 的 完全子集 所能取到的 最大元素和 。

完全平方数是指可以表示为一个整数和其自身相乘的数。

示例 1：

输入：nums = [8,7,3,5,7,2,4,9]
输出：16
解释：除了由单个下标组成的子集之外，还有两个下标集的完全子集：{1,4} 和 {2,8} 。
与下标 1 和 4 对应的元素和等于 nums[1] + nums[4] = 8 + 5 = 13 。
与下标 2 和 8 对应的元素和等于 nums[2] + nums[8] = 7 + 9 = 16 。
因此，下标集的完全子集可以取到的最大元素和为 16 。

示例 2：

输入：nums = [5,10,3,10,1,13,7,9,4]
输出：19
解释：除了由单个下标组成的子集之外，还有四个下标集的完全子集：{1,4}、{1,9}、{2,8}、{4,9} 和 {1,4,9} 。 
与下标 1 和 4 对应的元素和等于 nums[1] + nums[4] = 5 + 10 = 15 。 
与下标 1 和 9 对应的元素和等于 nums[1] + nums[9] = 5 + 4 = 9 。 
与下标 2 和 8 对应的元素和等于 nums[2] + nums[8] = 10 + 9 = 19 。
与下标 4 和 9 对应的元素和等于 nums[4] + nums[9] = 10 + 4 = 14 。 
与下标 1、4 和 9 对应的元素和等于 nums[1] + nums[4] + nums[9] = 5 + 10 + 4 = 19 。 
因此，下标集的完全子集可以取到的最大元素和为 19 。

提示：

1 <= n == nums.length <= 10⁴
1 <= nums[i] <= 10⁹

Submission

运行时间: 52 ms

内存: 17.4 MB

MX = 10001
core = [0] * MX
for i in range(1, MX):
    if core[i] == 0:  # i 不含完全平方因子，可以作为 core 值
        for j in range(1, isqrt(MX // i) + 1):
            core[i * j * j] = i

class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        s = [0] * (len(nums) + 1)
        for i, x in enumerate(nums, 1):  # 下标从 1 开始
            s[core[i]] += x
        return max(s)

Explain

此题解的核心思想是通过预计算每个数的“核心”值，该核心值是除去所有平方因子后剩下的部分。例如，对于数字12，其分解为2^2 * 3，去掉平方因子2^2后，剩下的核心值是3。这样，任何两个数如果它们的核心值相同，那么这两个数的乘积就是一个完全平方数。这是因为它们各自的非平方部分相乘后，剩下的就只有平方因子的乘积，仍然是一个完全平方数。\n解决方案中首先预处理一个数组`core`，其中`core[i]`表示数字`i`的核心值。然后，遍历给定数组`nums`，用一个数组`s`来记录每个核心值对应的元素之和。最后，返回`s`数组中的最大值，这就是所有可能的完全子集中的最大元素和。

时间复杂度: O(n*sqrt(n))

空间复杂度: O(n)

# 定义最大值
MX = 10001
# 初始化 core 数组，用于存储每个整数的核心值
core = [0] * MX
# 预处理 core 数组
for i in range(1, MX):
    if core[i] == 0:  # 如果当前数的核心值未被设置
        for j in range(1, isqrt(MX // i) + 1):  # 对于每个可能的平方数
            core[i * j * j] = i  # 设置核心值

# 解题类
class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        # 初始化和数组
        s = [0] * (len(nums) + 1)
        # 遍历 nums 数组
        for i, x in enumerate(nums, 1):  # nums 的下标从 1 开始
            s[core[i]] += x  # 将 nums[i] 加到其核心值对应的位置
        return max(s)  # 返回 s 中的最大值

Explore

核心值的概念是通过除去一个数字的所有平方因子，得到该数字的核心数值，这个数值帮助我们识别和归类哪些数字可以组成完全平方数。在这个题目中，如果两个数字的核心值相同，那么它们去掉平方因子后的部分相乘仍然是一个完全平方数。这种方法将问题从判断任意两个数的乘积是否为完全平方数简化为判断它们核心值是否相同，从而极大地简化了计算过程和时间复杂度。通过这种方式，我们可以将具有相同核心值的所有元素组合在一起，并计算它们的和，最终求得这些组合中可能的最大和。

在预处理core数组时，我们的目标是为每个整数设置一个核心值，即除去该整数的所有平方因子后剩下的部分。对于每个整数i，我们需要考虑所有可能将i作为因子的平方数。这里使用isqrt(MX // i)是因为对于任何大于sqrt(MX // i)的数j，i * j * j将超过我们预处理数组的大小上限MX。因此，迭代到isqrt(MX // i)确保了我们不会超出数组边界，同时能够考虑到所有可能的平方数因子。

您的观察是正确的。在题解中的for循环应该使用core[x]而不是core[i]索引数组s，因为core[i]表示的是数字i的核心值，而我们需要的是nums数组中每个元素x的核心值。如果使用core[i]代替core[x]，那么算法将错误地索引和更新数组s，导致计算出的最大和不正确。这将影响算法的正确性和输出的准确性。

将s数组的长度设置为len(nums)+1是一个显然的错误。正确的做法应该是根据不同核心值的可能数量来设置数组s的长度，这通常是小于或等于MX。因为核心值的范围决定了s数组需要多大，而不是输入数组nums的长度。如果按照nums的长度来设置s数组，可能会导致数组越界或内存浪费，因为有些核心值可能并不存在于nums中。正确的做法是分析给定的数据范围和核心值的计算方式，据此设置合理的数组长度。