> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/array/hard/2862.-maximum-element-sum-of-a-complete-subset-of-indices.md).

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

## Problem Statement

<br>

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.

&#x20;

**Example 1:**

<pre><code><strong>Input: nums = [8,7,3,5,7,2,4,9]
</strong><strong>Output: 16
</strong><strong>Explanation: Apart from the subsets consisting of a single index, there are two other complete subsets of indices: {1,4} and {2,8}.
</strong>The sum of the elements corresponding to indices 1 and 4 is equal to nums[1] + nums[4] = 8 + 5 = 13.
The sum of the elements corresponding to indices 2 and 8 is equal to nums[2] + nums[8] = 7 + 9 = 16.
Hence, the maximum element-sum of a complete subset of indices is 16.
</code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [5,10,3,10,1,13,7,9,4]
</strong><strong>Output: 19
</strong><strong>Explanation: Apart from the subsets consisting of a single index, there are four other complete subsets of indices: {1,4}, {1,9}, {2,8}, {4,9}, and {1,4,9}.
</strong>The sum of the elements conrresponding to indices 1 and 4 is equal to nums[1] + nums[4] = 5 + 10 = 15.
The sum of the elements conrresponding to indices 1 and 9 is equal to nums[1] + nums[9] = 5 + 4 = 9.
The sum of the elements conrresponding to indices 2 and 8 is equal to nums[2] + nums[8] = 10 + 9 = 19.
The sum of the elements conrresponding to indices 4 and 9 is equal to nums[4] + nums[9] = 10 + 4 = 14.
The sum of the elements conrresponding to indices 1, 4, and 9 is equal to nums[1] + nums[4] + nums[9] = 5 + 10 + 4 = 19.
Hence, the maximum element-sum of a complete subset of indices is 19.
</code></pre>

&#x20;

**Constraints:**

* `1 <= n == nums.length <= 104`
* `1 <= nums[i] <= 109`

## Intuition

```
Approach:

We tend to eliminate the perfect squares repeatedly
Eg->
nums  8,7,3,5,7,2,4,9
index 0 1 2 3 4 5 6 7

take ->   4/(4) -> 1 

1 4 9
1 ->will be saved
4/4 -> will be added to 1
9/9 -> will be added to 1


We take all perfect squares until number (index)
And remove till we get a residue 
Which is not a perfect square

Then we have another number , With same residue , Which will be added to that to make
It a perfect square

eg->

24 -> 4*6 , We need extra 6 
```

### Links

<https://leetcode.com/problems/maximum-element-sum-of-a-complete-subset-of-indices/description/>

### Video Links

<https://www.youtube.com/watch?v=wlaDBN_CJKg&ab_channel=AryanMittal>

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    long long maximumSum(vector<int>& nums) {
        unordered_map<int, long long> count;
        long long res = 0;

        for(int i=0; i<nums.size(); i++){
            long long num = i+1;
            for(long long v=2; v*v<=num; v++){
                while(num % (v*v) == 0)
                    num /= v*v;
            }

            res = max(res, count[num] += nums[i]);
        }

        return res;
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###