Maximize Subarray GCD Score

• Initialize max_score to 0.
• Iterate through each possible starting index i from 0 to n-1.
  • Generate a set of candidate GCDs, cand_divs, by finding all divisors of nums[i] and 2 * nums[i]. This is because the final GCD of any subarray starting at i must divide the first element of the modified subarray.
  • Initialize a map, costs, to store the cumulative cost for each candidate divisor d in cand_divs for the subarray starting at i.
  • Iterate through each possible ending index j from i to n-1.
    • For each candidate divisor d in cand_divs that is still considered valid:
      • Calculate the cost to make nums[j] a multiple of d. This cost is 0, 1, or infinity.
      • If the cost is infinity, d is no longer a valid candidate for subarrays extending further. We can effectively remove it.
      • Otherwise, add this cost to costs[d].
      • If the total costs[d] is less than or equal to k, it means we can achieve a GCD of d for the subarray nums[i...j]. Update the max_score with (j - i + 1) * d.
• Return max_score.

We can iterate through all possible start and end indices, i and j, to define a subarray nums[i...j]. For each subarray, we need to find the best possible GCD. A crucial observation is that if a subarray nums[i...j] is modified to have a GCD of g, then g must divide every element in the modified subarray. In particular, g must divide the modified version of nums[i]. Therefore, g must be a divisor of either nums[i] or 2 * nums[i].

This observation gives us a strategy: for each starting position i, we generate all divisors of nums[i] and 2 * nums[i] as candidate GCDs. Then, for each subarray nums[i...j] starting at i, we check each candidate GCD d. We calculate the total number of operations (cost) required to make all elements from nums[i] to nums[j] divisible by d. If this cost does not exceed k, we calculate the score (j - i + 1) * d and update our overall maximum score. To optimize, as we extend the subarray from j to j+1, we can update the costs for each candidate d incrementally.

1import java.util.*;2 3class Solution {4    private long costForElement(long num, long g) {5        if (num % g == 0) {6            return 0;7        }8        if (g % 2 != 0) {9            return Integer.MAX_VALUE; // Cannot make it a multiple of an odd g by doubling10        }11        if ((num * 2) % g == 0) {12            return 1;13        }14        return Integer.MAX_VALUE;15    }16 17    private Set<Integer> getDivisors(int n) {18        Set<Integer> divisors = new HashSet<>();19        for (int i = 1; i * i <= n; i++) {20            if (n % i == 0) {21                divisors.add(i);22                divisors.add(n / i);23            }24        }25        return divisors;26    }27 28    public long maxScore(int[] nums, int k) {29        int n = nums.length;30        long maxScore = 0;31 32        for (int i = 0; i < n; i++) {33            Set<Integer> candDivs = getDivisors(nums[i]);34            candDivs.addAll(getDivisors(2 * nums[i]));35 36            Map<Integer, Long> costs = new HashMap<>();37            for (int d : candDivs) {38                costs.put(d, 0L);39            }40 41            for (int j = i; j < n; j++) {42                List<Integer> toRemove = new ArrayList<>();43                for (int d : costs.keySet()) {44                    long c = costForElement(nums[j], d);45                    if (c > k) { // Using MAX_VALUE, so this check is fine46                        toRemove.add(d);47                    } else {48                        costs.put(d, costs.get(d) + c);49                    }50                }51                for (int d : toRemove) {52                    costs.remove(d);53                }54 55                for (Map.Entry<Integer, Long> entry : costs.entrySet()) {56                    if (entry.getValue() <= k) {57                        long currentScore = (long)(j - i + 1) * entry.getKey();58                        maxScore = Math.max(maxScore, currentScore);59                    }60                }61            }62        }63        return maxScore;64    }65}

• First, generate a set S of all unique candidate GCDs. A key insight is that any optimal GCD must be a divisor of some nums[i] or 2 * nums[i]. We can build S by iterating through each number in nums, finding all divisors of it and its doubled value, and adding them to the set.
• Initialize max_score to 0.
• Iterate through each candidate GCD g in the set S.
  • For the current g, create a cost array of size n. For each i, cost[i] will be the number of operations (0 or 1) to make nums[i] a multiple of g. If it's impossible, the cost can be considered infinite.
  • The problem now is to find the longest contiguous subarray in the cost array whose elements sum to at most k.
  • This can be solved efficiently in O(n) time using a sliding window approach.
    • Maintain a window [start, end] and the current_cost of elements within it.
    • Expand the window by incrementing end and adding cost[end] to current_cost.
    • If current_cost exceeds k, shrink the window from the left by incrementing start and subtracting cost[start].
    • In each step, the valid window size is end - start + 1. Keep track of the maximum length L found.
  • Once the maximum length L for g is found, calculate the potential score L * g and update max_score.
• Return max_score.

The core idea is that the GCD of an optimal subarray nums[i...j] must divide the modified first element a_i, which is either nums[i] or 2*nums[i]. This implies that any possible optimal GCD must be a divisor of nums[i] or 2*nums[i] for some i. We can thus pre-compute a set S of all such divisors from all numbers in the input array. This set S contains all candidate values for the optimal GCD.

For each candidate GCD g from S, we determine the feasibility and find the best possible score. We can create a cost array where cost[i] is 0 if nums[i] is a multiple of g, 1 if nums[i] is not but 2*nums[i] is, and infinity otherwise. The problem then becomes finding the longest subarray in this cost array with a total sum no more than k. This is a classic sliding window problem. We iterate through the cost array with a window, expanding it to the right and shrinking it from the left whenever the sum of costs within the window exceeds k. This allows us to find the maximum length subarray for a given g in O(n) time. By doing this for every g in S, we can find the overall maximum score.

1import java.util.*;2 3class Solution {4    private int costForElement(long num, int g) {5        if (num % g == 0) {6            return 0;7        }8        // If g is odd, we can't make num a multiple of g by doubling if it's not already.9        // (num * 2) % g == 0 implies num % (g/gcd(g,2)) == 0.10        // If g is odd, gcd(g,2)=1, so num % g == 0, which is a contradiction.11        if (g % 2 != 0) {12            return Integer.MAX_VALUE;13        }14        if ((num * 2) % g == 0) {15            return 1;16        }17        return Integer.MAX_VALUE;18    }19 20    private void findDivisors(int n, Set<Integer> divisors) {21        for (int i = 1; i * i <= n; i++) {22            if (n % i == 0) {23                divisors.add(i);24                divisors.add(n / i);25            }26        }27    }28 29    public long maxScore(int[] nums, int k) {30        int n = nums.length;31        Set<Integer> candidateGCDs = new HashSet<>();32        for (int num : nums) {33            findDivisors(num, candidateGCDs);34            if (2L * num <= Integer.MAX_VALUE) { // Avoid overflow for divisor finding35                 findDivisors(2 * num, candidateGCDs);36            }37        }38 39        long maxScore = 0;40 41        for (int g : candidateGCDs) {42            int[] costs = new int[n];43            for (int i = 0; i < n; i++) {44                costs[i] = costForElement(nums[i], g);45            }46 47            int start = 0;48            long currentCost = 0;49            int maxLength = 0;50 51            for (int end = 0; end < n; end++) {52                currentCost += costs[end];53                while (currentCost > k) {54                    currentCost -= costs[start];55                    start++;56                }57                maxLength = Math.max(maxLength, end - start + 1);58            }59            maxScore = Math.max(maxScore, (long)maxLength * g);60        }61 62        return maxScore;63    }64}