Maximum Element-Sum of a Complete Subset of Indices

This is an optimized version of the first approach. It recognizes that calculating the square-free part for each index from scratch is inefficient. By precomputing the square-free parts for all numbers from 1 to n using a sieve, we can reduce the time complexity significantly. The sieve efficiently removes all perfect square factors from each number in nearly linear time. Once the precomputation is done, the problem is solved by grouping and summing the elements, just like in the previous approach, but with a much faster lookup for the square-free parts.

• This approach uses the same fundamental principle of grouping indices by their square-free part.
• To improve efficiency, it avoids re-calculating the square-free part for each index individually.
• Instead, it precomputes the square-free parts for all numbers from 1 to n using a sieve-like algorithm.
• The sieve works by iterating through numbers j and for each j, removing the perfect square factor j*j from all its multiples up to n.
• After this O(n) precomputation, the main logic proceeds as before: iterate through indices, look up the precomputed square-free part, and aggregate sums in a hash map.

The bottleneck in the previous approach is the repeated calculation within the main loop. We can optimize this by pre-calculating all necessary square-free parts at once.

Algorithm Steps:

1. Precomputation with a Sieve:
   • Create an integer array sf of size n + 1.
   • Initialize sf[i] = i for all i from 1 to n.
   • Iterate with a number j from 2 up to n. If j*j > n, we can stop.
   • For each j, let square = j * j.
   • Iterate through all multiples of square up to n (i.e., m = square, 2*square, 3*square, ...).
   • For each multiple m, repeatedly divide sf[m] by square until it's no longer divisible. This effectively removes the perfect square factor j*j from sf[m].
2. Grouping and Summation:
   • Initialize a HashMap<Integer, Long> called groupSums.
   • Iterate with an index i from 1 to n.
   • The square-free part of i is now a simple lookup: core = sf[i].
   • Add nums[i-1] to the sum for the group core in the groupSums map.
3. Find Maximum:
   • Find and return the maximum value present in the groupSums map.

This precomputation step changes the overall time complexity from O(n * sqrt(n)) to nearly O(n).

import java.util.HashMap;
import java.util.Map;

class Solution {
    public long maximumSum(int[] nums) {
        int n = nums.length;
        
        // Step 1: Precompute square-free parts for 1 to n using a sieve
        int[] sf = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            sf[i] = i;
        }
        
        for (int j = 2; j * j <= n; j++) {
            int square = j * j;
            for (int m = square; m <= n; m += square) {
                while (sf[m] % square == 0) {
                    sf[m] /= square;
                }
            }
        }
        
        // Step 2: Group sums based on the precomputed square-free parts
        Map<Integer, Long> groupSums = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            int core = sf[i]; // O(1) lookup
            long currentVal = nums[i - 1];
            groupSums.put(core, groupSums.getOrDefault(core, 0L) + currentVal);
        }
        
        // Step 3: Find the maximum sum among all groups
        long maxSum = 0;
        for (long sum : groupSums.values()) {
            maxSum = Math.max(maxSum, sum);
        }
        
        return maxSum;
    }
}