Maximize Subarray GCD Score

Maximize Subarray GCD Score

What is this problem about?

The Maximize Subarray GCD Score problem asks you to find a contiguous subarray within an array of integers that maximizes a specific score. The score is typically defined as the product of the Greatest Common Divisor (GCD) of the subarray and its length, or the GCD multiplied by the sum of the subarray. The goal is to traverse the array and dynamically calculate this score for all valid subarrays to find the maximum possible value.

Why is this asked in interviews?

This is a Hard-level Number Theory and Array optimization problem. Interviewers ask it because computing the GCD for every possible subarray naively takes $O(N^3)$ or $O(N^2)$ time, which will fail on large inputs. It tests whether a candidate knows how to leverage the property that the GCD of a sequence can only decrease as the sequence grows, meaning the number of distinct GCDs ending at any index is incredibly small (bounded by $\log(\text{Max\_Value})$).

Algorithmic pattern used

This problem relies on Math (Number Theory) and Dynamic Array (State Tracking). Instead of checking all pairs, we maintain a list of (gcd_value, start_index) pairs representing all the unique GCDs of subarrays ending at the previous index. When we move to the current_index, we take the new number, and for every (gcd_value, start_index) in our list, we calculate new_gcd = GCD(gcd_value, current_number). We also add (current_number, current_index) to this list. Because many prefixes will result in the same new_gcd, we merge duplicates, keeping only the earliest start_index to maximize subarray length/sum. We then calculate the score for each unique GCD and update our global max.

Example explanation

Assume we want to maximize GCD * length. Array: [2, 4, 8]

• Index 0 (2): Current GCDs: [(2, idx 0)]. Score = $2 \times (0 - 0 + 1) = 2$. Max = 2.
• Index 1 (4):
  • Update previous: GCD(2, 4) = 2, starts at 0.
  • Add current: GCD(4, 4) = 4, starts at 1.
  • Current GCDs: [(2, idx 0), (4, idx 1)].
  • Scores: for 2 -> $2 \times 2 = 4$. For 4 -> $4 \times 1 = 4$. Max = 4.
• Index 2 (8):
  • Update previous: GCD(2, 8) = 2 (idx 0), GCD(4, 8) = 4 (idx 1).
  • Add current: GCD(8, 8) = 8 (idx 2).
  • Current GCDs: [(2, 0), (4, 1), (8, 2)].
  • Scores: $2 \times 3 = 6$. $4 \times 2 = 8$. $8 \times 1 = 8$. The maximum score is 8.

Common mistakes candidates make

The most common mistake is writing a standard $O(N^2)$ nested loop to calculate the GCD of every subarray [i...j]. This will easily Time Limit Exceed. Another mistake is failing to deduplicate the list of active GCDs at each step. If you don't merge identical GCD values (keeping the most advantageous index), the list of active GCDs will grow to size $N$, ruining the optimization.

Interview preparation tip

For the Maximize Subarray GCD Score coding problem, memorize the "Running GCDs" trick. The number of distinct GCDs for any subarray ending at index $i$ is at most the number of prime factors of arr[i], which is logarithmically small. Maintaining a small list or Hash Map of current_gcds and updating it step-by-step is a powerful template for any "Subarray GCD" or "Subarray Bitwise OR/AND" problem.