3020. Find the Maximum Number of Elements in Subset

You are given an array of positive integers nums.

You need to select a subset of nums which satisfies the following condition:

• You can place the selected elements in a 0-indexed array such that it follows the pattern: [x, x2, x4, ..., xk/2, xk, xk/2, ..., x4, x2, x] (Note that k can be be any non-negative power of 2). For example, [2, 4, 16, 4, 2] and [3, 9, 3] follow the pattern while [2, 4, 8, 4, 2] does not.

Return the maximum number of elements in a subset that satisfies these conditions.

class Solution {
public:
    int maximumLength(vector<int>& nums) {
        map<long long, int> freq;
        unordered_map<long long, int> dp;
        for(auto& n : nums) freq[n] += 1;
        int res = 1;
        if(freq.count(1)) {
            int x = freq[1];
            if(x % 2 == 0) x -= 1;
            res = max(res, x);
        }
        for(auto& [k,v] : freq) {
            if(dp.count(k)) res = max(res, 1 + dp[k]);
            if(v >= 2) {
                long long kk = k * k;
                long long cnt = 2l;
                if(dp.count(k)) cnt += dp[k];
                dp[kk] = cnt;
            }
        }
        return res;
    }
};