Maximum Element-Sum of a Complete Subset of Indices
You are given a 1-indexed array nums. Your task is to select a complete subset from nums where every pair of selected indices multiplied is a perfect square; that is, if you select nums[i] and nums[j], then i * j must be a perfect square.
Return the sum of the complete subset with the maximum sum.
Example 1
Input
nums = [8,7,3,5,7,2,4,9]Output
16We select elements at indices 2 and 8, and 2 * 8 is a perfect square.
Example 2
Input
nums = [8,10,3,8,1,13,7,9,4]Output
20We select elements at indices 1, 4, and 9; 1 * 4, 1 * 9, and 4 * 9 are perfect squares.
Constraints
- 1 <= n == nums.length <= 10^4
- 1 <= nums[i] <= 10^9