2862. Maximum Element-Sum of a Complete Subset of Indices

You are given a 1**-indexed** array nums of n integers.

A set of numbers is complete if the product of every pair of its elements is a perfect square.

For a subset of the indices set {1, 2, ..., n} represented as {i1, i2, ..., ik}, we define its element-sum as: nums[i1] + nums[i2] + ... + nums[ik].

Return the maximum element-sum of a complete subset of the indices set {1, 2, ..., n}.

A perfect square is a number that can be expressed as the product of an integer by itself.

class Solution {
    long long helper(long long k) {
        long long res = 1;
        for(int i = 2; i * i <= k; i++) {
            if(k % i) continue;
            int cnt = 0;
            while(k % i == 0) {
                k /= i, cnt += 1;
            }
            if(cnt & 1) res *= i;
        }
        if(k != 1) res *= k;
        return res;
    }
public:
    long long maximumSum(vector<int>& nums) {
        unordered_map<long long, long long> mp;
        long long res = 0;
        for(int i = 0; i < nums.size(); i++) {
            long long k = helper(i + 1);
                mp[k] += nums[i];
                res = max(res, mp[k]);
        }
        return res;
    }
};