2862. 完全子集的最大元素和 (opens new window)

1.平方数枚举

解题思路：枚举出每一个完全集，并计算对应下标结果。关键在于什么样的数可以加入完全集？

• 对于任意数拆分成完全平方数和另一个数的乘积k=i * j * j，可以发现每一个完全集中的数字 i 都是相同的。比如,2*4,2*9,2*16...)应该放在同一个集合中
• 枚举i，得到对应的完全集，并计算每个元素和。

✨在平方数枚举时，除了使用sqrt计算以外，使用for(int j=1;i*j*j<=nums.size();j++)的方式可以减少复杂度。因为这里是需要计算平方数，而不是要"判断"完全平方数。

class Solution {
    public long maximumSum(List<Integer> nums) {
        long res=Integer.MIN_VALUE;
        for(int i=1;i<=nums.size();i++){
            long sum=0;
            for(int j=1;i*j*j<=nums.size();j++){
                sum+=nums.get(i*j*j-1);
            }
            res=Math.max(res,sum);
        }
        return res;
    }
}