Maximum GCD-Sum of a Subarray - Solution & Explanation

Problem Overview: You are given an integer array and need the maximum value of gcd(subarray) * sum(subarray) for any valid subarray. The challenge is computing GCDs across many ranges while still tracking subarray sums efficiently.

Approach 1: Brute Force with Incremental GCD (O(n² log V) time, O(1) space)

Start every subarray at index i and extend it one element at a time to the right. Maintain the running GCD as you expand the window using gcd(current_gcd, nums[j]). Track the running sum or compute it using prefix sums, then update the answer with gcd * sum. This approach checks all O(n²) subarrays and each GCD update costs O(log V), where V is the value range. It works for small inputs but quickly becomes too slow for large arrays.

Approach 2: GCD Compression + Prefix Sum (O(n log V) time, O(log V) space)

Instead of recomputing the GCD for every subarray independently, keep a compressed list of all distinct GCD values for subarrays ending at the current index. When you move to index r, extend every previous GCD segment by computing gcd(prev_gcd, nums[r]), and also start a new segment with nums[r]. Many segments collapse to the same GCD, so you merge them and keep the earliest starting index. This keeps the number of active GCD states small (typically O(log V)).

Use a prefix sum array to compute subarray sums in O(1). For each compressed state (g, start), calculate the subarray sum ending at r and update the candidate value g * sum. Because each index only produces a limited number of distinct GCD states, the total work across the array remains near linear.

This technique appears frequently in number theory problems involving subarray GCDs. Prefix sums provide constant-time range sums, a common pattern in array problems. Efficient GCD merging prevents the quadratic explosion that the brute-force method suffers from.

Recommended for interviews: The compressed GCD approach with prefix sums is what interviewers expect for a hard problem in math and number theory. Brute force shows you understand the definition of subarray GCDs, but the optimized method demonstrates algorithmic maturity by reusing previously computed GCD states and reducing the search space from quadratic to near linear.