Watch 10 video solutions for Maximum Element-Sum of a Complete Subset of Indices, a hard level problem involving Array, Math, Number Theory. This walkthrough by Ashish Pratap Singh has 1,002,273 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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,. i. e. if you select ai and aj, 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: 16
Explanation:
We 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: 20
Explanation:
We select elements at indices 1, 4, and 9. 1 * 4, 1 * 9, 4 * 9 are perfect squares.
Constraints:
1 <= n == nums.length <= 1041 <= nums[i] <= 109