# Maximize Subarray GCD Score
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximize-subarray-gcd-score)
Canonical: https://scaleengineer.com/dsa/problems/maximize-subarray-gcd-score
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Data structures:** Array
---
## Problem
You are given an array of positive integers `nums` and an integer `k`.

You may perform at most `k` operations. In each operation, you can choose one element in the array and **double** its value. Each element can be doubled **at most** once.

The **score** of a contiguous **subarray** is defined as the **product** of its length and the _greatest common divisor (GCD)_ of all its elements.

Your task is to return the **maximum** **score** that can be achieved by selecting a contiguous subarray from the modified array.

**Note:**

* The **greatest common divisor (GCD)** of an array is the largest integer that evenly divides all the array elements.

**Example 1:**

**Input:** nums = \[2,4\], k = 1

**Output:** 8

**Explanation:**

* Double `nums[0]` to 4 using one operation. The modified array becomes `[4, 4]`.
* The GCD of the subarray `[4, 4]` is 4, and the length is 2.
* Thus, the maximum possible score is `2 × 4 = 8`.

**Example 2:**

**Input:** nums = \[3,5,7\], k = 2

**Output:** 14

**Explanation:**

* Double `nums[2]` to 14 using one operation. The modified array becomes `[3, 5, 14]`.
* The GCD of the subarray `[14]` is 14, and the length is 1.
* Thus, the maximum possible score is `1 × 14 = 14`.

**Example 3:**

**Input:** nums = \[5,5,5\], k = 1

**Output:** 15

**Explanation:**

* The subarray `[5, 5, 5]` has a GCD of 5, and its length is 3.
* Since doubling any element doesn't improve the score, the maximum score is `3 × 5 = 15`.

**Constraints:**

* `1 <= n == nums.length <= 1500`
* `1 <= nums[i] <= 109`
* `1 <= k <= n`

# Approaches
## Brute-force over Subarrays
This approach systematically checks every possible contiguous subarray. For each subarray, it calculates the maximum possible GCD that can be achieved using at most `k` doubling operations. The main idea is that for any subarray starting at index `i`, the greatest common divisor `g` of its modified version must be a divisor of the first element's modified value (either `nums[i]` or `2*nums[i]`). This allows us to limit the set of candidate GCDs we need to test for all subarrays starting at `i`.
**Time:** O(n^2 * D_max), where `n` is the length of the array and `D_max` is the maximum number of divisors. The outer loop runs `n` times for `i`, the inner loop runs up to `n` times for `j`, and for each subarray, we iterate through `D_max` candidate divisors. This is too slow for the given constraints. · **Space:** O(D_max), where `D_max` is the maximum number of divisors for any number in the input range. This space is used to store candidate divisors and their costs for each starting index `i`.
**Pros:** Conceptually straightforward and builds upon a clear observation.; Correctly explores the solution space, although inefficiently.
**Cons:** The time complexity is high due to three nested loops (iterating `i`, `j`, and candidate divisors), making it too slow for the given constraints.
### Explanation
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.

```java
import java.util.*;

class Solution {
    private long costForElement(long num, long g) {
        if (num % g == 0) {
            return 0;
        }
        if (g % 2 != 0) {
            return Integer.MAX_VALUE; // Cannot make it a multiple of an odd g by doubling
        }
        if ((num * 2) % g == 0) {
            return 1;
        }
        return Integer.MAX_VALUE;
    }

    private Set<Integer> getDivisors(int n) {
        Set<Integer> divisors = new HashSet<>();
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                divisors.add(i);
                divisors.add(n / i);
            }
        }
        return divisors;
    }

    public long maxScore(int[] nums, int k) {
        int n = nums.length;
        long maxScore = 0;

        for (int i = 0; i < n; i++) {
            Set<Integer> candDivs = getDivisors(nums[i]);
            candDivs.addAll(getDivisors(2 * nums[i]));

            Map<Integer, Long> costs = new HashMap<>();
            for (int d : candDivs) {
                costs.put(d, 0L);
            }

            for (int j = i; j < n; j++) {
                List<Integer> toRemove = new ArrayList<>();
                for (int d : costs.keySet()) {
                    long c = costForElement(nums[j], d);
                    if (c > k) { // Using MAX_VALUE, so this check is fine
                        toRemove.add(d);
                    } else {
                        costs.put(d, costs.get(d) + c);
                    }
                }
                for (int d : toRemove) {
                    costs.remove(d);
                }

                for (Map.Entry<Integer, Long> entry : costs.entrySet()) {
                    if (entry.getValue() <= k) {
                        long currentScore = (long)(j - i + 1) * entry.getKey();
                        maxScore = Math.max(maxScore, currentScore);
                    }
                }
            }
        }
        return maxScore;
    }
}
```
### Algorithm
*   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`.

## Iterate Over All Potential GCDs
Instead of iterating through subarrays, a more efficient approach is to iterate through all possible values of the final GCD. For each potential GCD value `g`, we can then efficiently find the longest subarray that can be modified to have `g` as its GCD within the `k` operation budget. This transforms the problem into a series of simpler subproblems, one for each candidate GCD.
**Time:** O(|S| * n + n * sqrt(M)), where `|S|` is the number of unique candidate GCDs, `n` is the array length, and `M` is the maximum value in `nums`. Generating `S` takes roughly `O(n * sqrt(M))`. The main loop runs `|S|` times, with each iteration taking `O(n)` for the sliding window. While `|S|` can be large in the worst case (`O(n * D_max)`), it's often much smaller in practice. · **Space:** O(|S| + n), where `|S|` is the total number of unique candidate divisors. `O(|S|)` space is needed to store the set of GCDs, and `O(n)` is used for the `cost` array within the loop.
**Pros:** More efficient than the subarray brute-force approach, especially when the number of unique divisors is small.; Reduces the problem to a standard, efficiently solvable subproblem (sliding window).
**Cons:** The number of unique candidate GCDs, `|S|`, can be large in the worst case, potentially leading to a slow runtime.; Requires significant memory to store the set of all candidate GCDs.
### Explanation
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.

```java
import java.util.*;

class Solution {
    private int costForElement(long num, int g) {
        if (num % g == 0) {
            return 0;
        }
        // If g is odd, we can't make num a multiple of g by doubling if it's not already.
        // (num * 2) % g == 0 implies num % (g/gcd(g,2)) == 0.
        // If g is odd, gcd(g,2)=1, so num % g == 0, which is a contradiction.
        if (g % 2 != 0) {
            return Integer.MAX_VALUE;
        }
        if ((num * 2) % g == 0) {
            return 1;
        }
        return Integer.MAX_VALUE;
    }

    private void findDivisors(int n, Set<Integer> divisors) {
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                divisors.add(i);
                divisors.add(n / i);
            }
        }
    }

    public long maxScore(int[] nums, int k) {
        int n = nums.length;
        Set<Integer> candidateGCDs = new HashSet<>();
        for (int num : nums) {
            findDivisors(num, candidateGCDs);
            if (2L * num <= Integer.MAX_VALUE) { // Avoid overflow for divisor finding
                 findDivisors(2 * num, candidateGCDs);
            }
        }

        long maxScore = 0;

        for (int g : candidateGCDs) {
            int[] costs = new int[n];
            for (int i = 0; i < n; i++) {
                costs[i] = costForElement(nums[i], g);
            }

            int start = 0;
            long currentCost = 0;
            int maxLength = 0;

            for (int end = 0; end < n; end++) {
                currentCost += costs[end];
                while (currentCost > k) {
                    currentCost -= costs[start];
                    start++;
                }
                maxLength = Math.max(maxLength, end - start + 1);
            }
            maxScore = Math.max(maxScore, (long)maxLength * g);
        }

        return maxScore;
    }
}
```
### Algorithm
*   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`.