Maximize Subarray GCD Score - Solution & Explanation

Problem Overview: You are given an integer array and must find the subarray that produces the maximum GCD-based score. The score depends on the greatest common divisor of the subarray combined with its length, so the goal is to evaluate subarrays efficiently without recomputing GCD values from scratch.

Approach 1: Brute Force Enumeration (O(n^3 log V) time, O(1) space)

The most direct approach enumerates every possible subarray and computes its GCD independently. For each pair of indices (i, j), iterate through the elements inside the range and compute the GCD from scratch using the Euclidean algorithm. After calculating the GCD, compute the score and track the maximum. This approach demonstrates the mathematical definition of GCD but performs repeated work because the same prefixes are recomputed many times. It quickly becomes impractical for large arrays.

Approach 2: Enumeration with Rolling GCD (O(n^2 log V) time, O(1) space)

A better strategy keeps the GCD while expanding the subarray. Fix a starting index i, then extend the subarray one element at a time. Update the running GCD using g = gcd(g, nums[j]) instead of recomputing the entire segment. Each extension requires only one GCD operation, which costs O(log V). This removes the inner recomputation loop and reduces the complexity to quadratic. This technique relies heavily on properties from number theory and works well when constraints allow O(n²) enumeration.

Approach 3: Distinct GCD Compression (O(n log V) time, O(log V) space)

The optimal method uses the observation that the number of distinct GCD values for subarrays ending at a given index is small. Maintain a map or list of pairs representing (gcd_value, earliest_length) for all subarrays ending at the current index. When a new element arrives, compute new GCD values by combining it with previous ones and merge identical results. Each step only keeps distinct GCD states, which limits the count to roughly O(log V). This technique transforms the brute-force enumeration into a compressed dynamic process and is common in advanced array and math problems involving GCD propagation.

Recommended for interviews: Start with the rolling GCD enumeration to show understanding of how GCD behaves when extending a subarray. Then explain the distinct-GCD optimization that reduces the state space. Interviewers typically expect the compressed GCD approach because it demonstrates knowledge of number theory properties and efficient subarray enumeration.