# 2862. Maximum Element-Sum of a Complete Subset of Indices¶

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public: long long maximumSum(vector& nums) { long ans = 0; unordered_map oddPowerToSum; for (int i = 0; i < nums.size(); ++i) { const int oddPower = divideSquares(i + 1); ans = max(ans, oddPowerToSum[oddPower] += nums[i]); } return ans; } private: int divideSquares(int val) { for (int num = 2; num * num <= val; ++num) while (val % (num * num) == 0) val /= num * num; return val; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public long maximumSum(List nums) { long ans = 0; HashMap oddPowerToSum = new HashMap<>(); for (int i = 0; i < nums.size(); ++i) { final int oddPower = divideSquares(i + 1); ans = Math.max(ans, oddPowerToSum.merge(oddPower, (long) nums.get(i), Long::sum)); } return ans; } private int divideSquares(int val) { for (int num = 2; num * num <= val; ++num) while (val % (num * num) == 0) val /= num * num; return val; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution: def maximumSum(self, nums: List[int]) -> int: ans = 0 oddPowerToSum = collections.Counter() def divideSquares(val: int) -> int: for num in range(2, val + 1): while val % (num * num) == 0: val //= (num * num) return val for i, num in enumerate(nums): oddPower = divideSquares(i + 1) oddPowerToSum[oddPower] += num ans = max(ans, oddPowerToSum[oddPower]) return ans