Skip to content

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

Approach 1: $O(n)$ space

  • 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<int>& nums) {
    long ans = 0;
    unordered_map<int, long> 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<Integer> nums) {
    long ans = 0;
    HashMap<Integer, Long> 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

Approach 2: $O(1)$ space

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
 public:
  long long maximumSum(vector<int>& nums) {
    long ans = 0;

    for (int oddPower = 1; oddPower <= nums.size(); ++oddPower) {
      long sum = 0;
      for (int num = 1; num * num * oddPower <= nums.size(); ++num)
        sum += nums[oddPower * num * num - 1];
      ans = max(ans, sum);
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
  public long maximumSum(List<Integer> nums) {
    long ans = 0;

    for (int oddPower = 1; oddPower <= nums.size(); ++oddPower) {
      long sum = 0;
      for (int num = 1; num * num * oddPower <= nums.size(); ++num)
        sum += nums.get(oddPower * num * num - 1);
      ans = Math.max(ans, sum);
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def maximumSum(self, nums: list[int]) -> int:
    ans = 0

    for oddPower in range(1, len(nums) + 1):
      summ = 0
      for num in range(1, len(nums) + 1):
        if num * num * oddPower > len(nums):
          break
        summ += nums[oddPower * num * num - 1]
      ans = max(ans, summ)

    return ans