2862. Maximum Element-Sum of a Complete Subset of Indices
Description
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 <= 104
1 <= nums[i] <= 109
Solutions
Solution 1: Enumeration
We note that if a number can be expressed in the form of $k \times j^2$, then all numbers of this form have the same $k$.
Therefore, we can enumerate $k$ in the range $[1,..n]$, and then start enumerating $j$ from $1$, each time adding the value of $nums[k \times j^2 - 1]$ to $t$, until $k \times j^2 > n$. At this point, update the answer to $ans = \max(ans, t)$.
Finally, return the answer $ans$.
The time complexity is $O(n)$, where $n$ is the length of the array. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|