给你一个下标从 1 开始、由 n 个整数组成的数组。
如果一组数字中每对元素下标的乘积都是一个完全平方数，则称这组数字是一个完全集 。
返回下标集 {1, 2, ..., n} 的 完全子集所能取到的最大元素和
1. 数学方法
这里选择从下而上，类似质数筛的方式进行枚举满足条件的完备集合
思考完全集合具备怎么样的性质，相互乘积都是完全平方数，那他们除以相同的公因数后，得到的集合同样是完备集
懒得证明了，直接枚举基本完备子集[1,4,9,16..]的倍数
class Solution {
public:
long long maximumSum(vector<int> &nums) {
long long ans = 0;
int n = nums.size();
for (int i = 1; i <= n; i++) {
long long sum = 0;
for (int j = 1; i * j * j <= n; j++) {
sum += nums[i * j * j - 1]; // -1 是因为数组下标从 0 开始
}
ans = max(ans, sum);
}
return ans;
}
};