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 <= 1041 <= nums[i] <= 109
Solutions
Solution 1: Enumeration
We note that if a number can be expressed in the form of k × j2, 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 × j2 - 1] to t, until k × j2 > 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).
PythonJavaJavaC++GoTypeScript
class Solution:
def maximumSum(self, nums: List[int]) -> int:
n = len(nums)
ans = 0
for k in range(1, n + 1):
t = 0
j = 1
while k * j * j <= n:
t += nums[k * j * j - 1]
j += 1
ans = max(ans, t)
return ans(code-box)
class Solution {
public long maximumSum(List<Integer> nums) {
long ans = 0;
int n = nums.size();
boolean[] used = new boolean[n + 1];
int bound = (int) Math.floor(Math.sqrt(n));
int[] squares = new int[bound + 1];
for (int i = 1; i <= bound + 1; i++) {
squares[i - 1] = i * i;
}
for (int i = 1; i <= n; i++) {
long res = 0;
int idx = 0;
int curr = i * squares[idx];
while (curr <= n) {
res += nums.get(curr - 1);
curr = i * squares[++idx];
}
ans = Math.max(ans, res);
}
return ans;
}
}(code-box)
class Solution {
public long maximumSum(List<Integer> nums) {
long ans = 0;
int n = nums.size();
for (int k = 1; k <= n; ++k) {
long t = 0;
for (int j = 1; k * j * j <= n; ++j) {
t += nums.get(k * j * j - 1);
}
ans = Math.max(ans, t);
}
return ans;
}
}(code-box)
class Solution {
public:
long long maximumSum(vector<int>& nums) {
long long ans = 0;
int n = nums.size();
for (int k = 1; k <= n; ++k) {
long long t = 0;
for (int j = 1; k * j * j <= n; ++j) {
t += nums[k * j * j - 1];
}
ans = max(ans, t);
}
return ans;
}
};(code-box)
func maximumSum(nums []int) (ans int64) {
n := len(nums)
for k := 1; k <= n; k++ {
var t int64
for j := 1; k*j*j <= n; j++ {
t += int64(nums[k*j*j-1])
}
ans = max(ans, t)
}
return
}(code-box)
function maximumSum(nums: number[]): number {
let ans = 0;
const n = nums.length;
for (let k = 1; k <= n; ++k) {
let t = 0;
for (let j = 1; k * j * j <= n; ++j) {
t += nums[k * j * j - 1];
}
ans = Math.max(ans, t);
}
return ans;
}(code-box)
