Algorithms
Hard
2862
3047
Maximum Element-Sum of a Complete Subset of Indices
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.

Example 1:

Input: nums = [8,7,3,5,7,2,4,9]
Output: 16
Explanation: Apart from the subsets consisting of a single index, there are two other complete subsets of indices: {1,4} and {2,8}.
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.

Example 2:

Input: nums = [5,10,3,10,1,13,7,9,4]
Output: 19
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}.
The sum of the elements corresponding to indices 1 and 4 is equal to nums[1] + nums[4] = 5 + 10 = 15.
The sum of the elements corresponding to indices 1 and 9 is equal to nums[1] + nums[9] = 5 + 4 = 9.
The sum of the elements corresponding to indices 2 and 8 is equal to nums[2] + nums[8] = 10 + 9 = 19.
The sum of the elements corresponding to indices 4 and 9 is equal to nums[4] + nums[9] = 10 + 4 = 14.
The sum of the elements corresponding 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.


Constraints:

 * 1 <= n == nums.length <= 104
 * 1 <= nums[i] <= 109
"""
class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        
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.

Example 1:

Input: nums = [8,7,3,5,7,2,4,9]
Output: 16
Explanation: Apart from the subsets consisting of a single index, there are two other complete subsets of indices: {1,4} and {2,8}.
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.

Example 2:

Input: nums = [5,10,3,10,1,13,7,9,4]
Output: 19
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}.
The sum of the elements corresponding to indices 1 and 4 is equal to nums[1] + nums[4] = 5 + 10 = 15.
The sum of the elements corresponding to indices 1 and 9 is equal to nums[1] + nums[9] = 5 + 4 = 9.
The sum of the elements corresponding to indices 2 and 8 is equal to nums[2] + nums[8] = 10 + 9 = 19.
The sum of the elements corresponding to indices 4 and 9 is equal to nums[4] + nums[9] = 10 + 4 = 14.
The sum of the elements corresponding 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.


Constraints:

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


Please complete the code below to solve above prblem:
```python
class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        
```

my_solution = Solution()

test_input = { "nums": [8,7,3,5,7,2,4,9] }
assert my_solution.maximumSum(**test_input) == 16

test_input = { "nums": [5,10,3,10,1,13,7,9,4] }
assert my_solution.maximumSum(**test_input) == 19

test_input = { "nums": [1,1,1,1] }
assert my_solution.maximumSum(**test_input) == 2

test_input = { "nums": [1,100,100,1] }
assert my_solution.maximumSum(**test_input) == 100

test_input = { "nums": [998244353,998244353,998244353,998244353] }
assert my_solution.maximumSum(**test_input) == 1996488706

test_input = { "nums": [1000000000,1,1,1000000000] }
assert my_solution.maximumSum(**test_input) == 2000000000

test_input = { "nums": [1,1,1000000000,1] }
assert my_solution.maximumSum(**test_input) == 1000000000

test_input = { "nums": [5,10,3,10,1,13,7,20,4] }
assert my_solution.maximumSum(**test_input) == 30

test_input = { "nums": [5,3,3,10,1,13,7,67,4] }
assert my_solution.maximumSum(**test_input) == 70

test_input = { "nums": [35,45,29,16,42,49,25,19,46] }
assert my_solution.maximumSum(**test_input) == 97

test_input = { "nums": [34,43,47,50,45] }
assert my_solution.maximumSum(**test_input) == 84

test_input = { "nums": [4,31,45,34,44] }
assert my_solution.maximumSum(**test_input) == 45

test_input = { "nums": [12,5,49,26] }
assert my_solution.maximumSum(**test_input) == 49

test_input = { "nums": [41] }
assert my_solution.maximumSum(**test_input) == 41

test_input = { "nums": [38,9,37,11,20,43] }
assert my_solution.maximumSum(**test_input) == 49

test_input = { "nums": [47,50,17,49,12,22] }
assert my_solution.maximumSum(**test_input) == 96

test_input = { "nums": [23,13,17,3,21,23] }
assert my_solution.maximumSum(**test_input) == 26

test_input = { "nums": [38,28] }
assert my_solution.maximumSum(**test_input) == 38

test_input = { "nums": [16,31,37,29,28,34,25,36] }
assert my_solution.maximumSum(**test_input) == 67

test_input = { "nums": [19,46,37,44,4,40,24,17,49] }
assert my_solution.maximumSum(**test_input) == 112

test_input = { "nums": [28,40,37] }
assert my_solution.maximumSum(**test_input) == 40

test_input = { "nums": [19,6,30,23,25,45,15,2,3,46] }
assert my_solution.maximumSum(**test_input) == 46

test_input = { "nums": [5,16,4,13,37,44,49,7] }
assert my_solution.maximumSum(**test_input) == 49

test_input = { "nums": [40,8,19,26] }
assert my_solution.maximumSum(**test_input) == 66

test_input = { "nums": [3,37,2] }
assert my_solution.maximumSum(**test_input) == 37

test_input = { "nums": [1,5,35,20,32,18,6,49,34,15] }
assert my_solution.maximumSum(**test_input) == 55

test_input = { "nums": [25,31,4,20,45] }
assert my_solution.maximumSum(**test_input) == 45

test_input = { "nums": [32,3,25,15,37,37,21,24,8,33] }
assert my_solution.maximumSum(**test_input) == 55

test_input = { "nums": [13] }
assert my_solution.maximumSum(**test_input) == 13

test_input = { "nums": [41,25,20,28,40,22,37,43,6,32] }
assert my_solution.maximumSum(**test_input) == 75

test_input = { "nums": [23,9,7,24,30,34,10,47] }
assert my_solution.maximumSum(**test_input) == 56

test_input = { "nums": [11,31,1,34,8,20,15,20,49] }
assert my_solution.maximumSum(**test_input) == 94

test_input = { "nums": [41,21,4,15,25,38,26,7,6] }
assert my_solution.maximumSum(**test_input) == 62

test_input = { "nums": [46,31,28,34,12,40,11,31,8,25] }
assert my_solution.maximumSum(**test_input) == 88

test_input = { "nums": [50] }
assert my_solution.maximumSum(**test_input) == 50

test_input = { "nums": [41,43,17,35] }
assert my_solution.maximumSum(**test_input) == 76

test_input = { "nums": [20,6] }
assert my_solution.maximumSum(**test_input) == 20

test_input = { "nums": [43,18,10,19,20,9,49] }
assert my_solution.maximumSum(**test_input) == 62

test_input = { "nums": [3,39,29,5,6,36,38,26,14,10] }
assert my_solution.maximumSum(**test_input) == 65

test_input = { "nums": [47,2,48,16,10,3,45,20,39] }
assert my_solution.maximumSum(**test_input) == 102

test_input = { "nums": [11,47,27,17,7] }
assert my_solution.maximumSum(**test_input) == 47

test_input = { "nums": [48,17,41,23,40,9,3,26,44,34] }
assert my_solution.maximumSum(**test_input) == 115

test_input = { "nums": [47,2,42,10,15,44,35,50] }
assert my_solution.maximumSum(**test_input) == 57

test_input = { "nums": [45,48,50,24,23,14,2,33] }
assert my_solution.maximumSum(**test_input) == 81

test_input = { "nums": [7,39,27,39,43,42,31,37,15] }
assert my_solution.maximumSum(**test_input) == 76

test_input = { "nums": [10,36,23,31] }
assert my_solution.maximumSum(**test_input) == 41

test_input = { "nums": [27,27,13,37] }
assert my_solution.maximumSum(**test_input) == 64

test_input = { "nums": [34,17,26,13] }
assert my_solution.maximumSum(**test_input) == 47

test_input = { "nums": [9,42] }
assert my_solution.maximumSum(**test_input) == 42

test_input = { "nums": [23,42,4,28,30,36,30,39] }
assert my_solution.maximumSum(**test_input) == 81

test_input = { "nums": [10,28,28,21,25,14,38] }
assert my_solution.maximumSum(**test_input) == 38

test_input = { "nums": [40,34,26,9,23,15,23,27,49] }
assert my_solution.maximumSum(**test_input) == 98

test_input = { "nums": [27,42,40,2,1] }
assert my_solution.maximumSum(**test_input) == 42

test_input = { "nums": [48,19,21,21,32,20,50,41,49,30] }
assert my_solution.maximumSum(**test_input) == 118

test_input = { "nums": [10,13,6,39,9] }
assert my_solution.maximumSum(**test_input) == 49

test_input = { "nums": [50,37,24,4,10,43,35] }
assert my_solution.maximumSum(**test_input) == 54

test_input = { "nums": [39,24] }
assert my_solution.maximumSum(**test_input) == 39

test_input = { "nums": [21] }
assert my_solution.maximumSum(**test_input) == 21

test_input = { "nums": [20,15] }
assert my_solution.maximumSum(**test_input) == 20

test_input = { "nums": [23,27,42,3,33,36,43,32,27,48,40,22,5,36,48] }
assert my_solution.maximumSum(**test_input) == 64

test_input = { "nums": [39,46,12,14,25,37,24,44,6,38,4] }
assert my_solution.maximumSum(**test_input) == 90

test_input = { "nums": [36,5,23,17,32,47,23,41,18,44,21,4,22,6,21] }
assert my_solution.maximumSum(**test_input) == 71

test_input = { "nums": [46,26,37,17,15,26,45,45,17,42,16,14,36,40] }
assert my_solution.maximumSum(**test_input) == 80

test_input = { "nums": [46,40,16,48,24,1,13,15,6,5,12,15,4] }
assert my_solution.maximumSum(**test_input) == 100

test_input = { "nums": [11,27,28,26,4,22,10,49,4,23,30,6,5] }
assert my_solution.maximumSum(**test_input) == 76

test_input = { "nums": [37,17,17,18,10,28,47,38,43,20,10] }
assert my_solution.maximumSum(**test_input) == 98

test_input = { "nums": [12,17,9,30,38,20,28,36,34,15,4,15,48] }
assert my_solution.maximumSum(**test_input) == 76

test_input = { "nums": [28,32,22,9,33,26,10,15,15,37,33,48,2,14,35] }
assert my_solution.maximumSum(**test_input) == 70

test_input = { "nums": [35,28,45,34,49,45,38,15,36,33,15,16] }
assert my_solution.maximumSum(**test_input) == 105

test_input = { "nums": [50,18,24,30,6,49,3,20,22,19,25,35,30,33] }
assert my_solution.maximumSum(**test_input) == 102

test_input = { "nums": [10,19,37,1,31,6,2,37,10,1,36,48,7,40] }
assert my_solution.maximumSum(**test_input) == 85

test_input = { "nums": [45,49,32,44,12,39,8,7,3,48,37,27,41,20,18] }
assert my_solution.maximumSum(**test_input) == 92

test_input = { "nums": [40,9,16,40,9,28,29,36,4,17,29] }
assert my_solution.maximumSum(**test_input) == 84

test_input = { "nums": [21,32,24,39,2,13,37,33,50,43,9,43,14] }
assert my_solution.maximumSum(**test_input) == 110

test_input = { "nums": [36,25,21,29,42,40,16,41,22,24,45,7,33] }
assert my_solution.maximumSum(**test_input) == 87

test_input = { "nums": [32,33,7,45,23,13,45,4,15,12] }
assert my_solution.maximumSum(**test_input) == 92

test_input = { "nums": [10,7,1,15,12,22,34,3,36,44,10,12] }
assert my_solution.maximumSum(**test_input) == 61

test_input = { "nums": [26,4,44,3,37,50,27,22,48,14,12,3,39,31] }
assert my_solution.maximumSum(**test_input) == 77

test_input = { "nums": [47,48,8,24,1,17,32,13,19,25,15,30,12] }
assert my_solution.maximumSum(**test_input) == 90

test_input = { "nums": [31,18,11,28,7,34,32,38,47,44,1,13,46] }
assert my_solution.maximumSum(**test_input) == 106

test_input = { "nums": [47,12,35,10,37,36,44,38,19,31,28,21,3,34] }
assert my_solution.maximumSum(**test_input) == 76

test_input = { "nums": [19,47,46,5,7,42,35,3,39,2,1,31] }
assert my_solution.maximumSum(**test_input) == 77

test_input = { "nums": [15,50,14,27,37,44,11,38,23,39,27,36,22] }
assert my_solution.maximumSum(**test_input) == 88

test_input = { "nums": [31,31,18,24,9,27,33,10,23,38,44,4,17,11,14] }
assert my_solution.maximumSum(**test_input) == 78

test_input = { "nums": [38,27,13,20,36,23,6,7,37,20,49,31,25,12] }
assert my_solution.maximumSum(**test_input) == 95

test_input = { "nums": [6,21,11,15,17,47,50,14,24,18,38,19,48,43] }
assert my_solution.maximumSum(**test_input) == 50

test_input = { "nums": [31,4,1,5,50,46,14,17,13,14,17,39,46,18] }
assert my_solution.maximumSum(**test_input) == 50

test_input = { "nums": [39,13,6,45,44,14,44,37,24,20,21,47,6,6,5] }
assert my_solution.maximumSum(**test_input) == 108

test_input = { "nums": [17,16,48,41,7,39,50,29,2,33] }
assert my_solution.maximumSum(**test_input) == 60

test_input = { "nums": [3,8,19,47,29,4,16,31,11,30] }
assert my_solution.maximumSum(**test_input) == 61

test_input = { "nums": [20,1,46,36,35,32,49,14,48,25,17,50,22] }
assert my_solution.maximumSum(**test_input) == 104

test_input = { "nums": [49,20,12,42,33,21,29,30,35,4,5,50] }
assert my_solution.maximumSum(**test_input) == 126

test_input = { "nums": [36,1,8,14,39,2,31,23,10,46,42] }
assert my_solution.maximumSum(**test_input) == 60

test_input = { "nums": [33,29,23,4,48,31,31,26,11,39] }
assert my_solution.maximumSum(**test_input) == 55

test_input = { "nums": [33,36,31,21,2,41,14,36,6,1,22,13,34] }
assert my_solution.maximumSum(**test_input) == 72

test_input = { "nums": [35,32,43,20,4,13,6,19,36,20] }
assert my_solution.maximumSum(**test_input) == 91

test_input = { "nums": [16,41,16,41,11,39,40,7,24,28,13] }
assert my_solution.maximumSum(**test_input) == 81

test_input = { "nums": [32,24,29,24,29,45,10,37,22,35,37,28,15] }
assert my_solution.maximumSum(**test_input) == 78

test_input = { "nums": [45,8,19,1,33,2,32,40,16,33,44,27] }
assert my_solution.maximumSum(**test_input) == 62

test_input = { "nums": [3,42,14,18,1,20,19,7,37,3,2,3,48] }
assert my_solution.maximumSum(**test_input) == 58