Maximum GCD-Sum of a Subarray

Maximum GCD-Sum of a Subarray

What is this problem about?

The Maximum GCD-Sum of a Subarray coding problem asks you to find a contiguous subarray such that the product of its GCD and the sum of its elements is maximized. It combines two classical number theory operations — greatest common divisor and summation — into a single optimization objective. This duality is what makes it a hard problem, as optimizing for GCD and optimizing for sum are often at odds with each other.

Why is this asked in interviews?

ThoughtWorks and similar companies use this problem to evaluate candidates' depth in number theory and their ability to handle problems where two competing objectives must be balanced. It also tests knowledge of how GCD changes as a subarray grows — a non-trivial property. Candidates who understand that the number of distinct GCD values for subarrays ending at a given index is O(log(max_value)) can design efficient solutions; others get stuck in O(n²) or O(n³) approaches.

Algorithmic pattern used

The approach combines the distinct GCD enumeration technique with binary search or prefix sums. For every right endpoint, maintain a set of (gcd_value, leftmost_index) pairs representing all distinct GCDs for subarrays ending here. When you move the right pointer, you update this set by taking GCD of each stored value with the new element. Since GCD can only decrease or stay the same as you extend a subarray, the number of distinct values is O(log(max_element)). For each distinct GCD, you use prefix sums to find the best sum in the corresponding range.

Example explanation

Array: [6, 3, 9]

• Subarrays and their GCD * sum:
  • [6]: GCD=6, sum=6 → 36
  • [6,3]: GCD=3, sum=9 → 27
  • [6,3,9]: GCD=3, sum=18 → 54
  • [3]: GCD=3, sum=3 → 9
  • [3,9]: GCD=3, sum=12 → 36
  • [9]: GCD=9, sum=9 → 81
• Maximum = 81 from subarray [9]

The distinct GCD property ensures you don't recompute everything from scratch at each step.

Common mistakes candidates make

• Brute-forcing all subarrays: O(n²) GCD computations with O(n) sum each leads to O(n³), which times out on large inputs.
• Not maintaining distinct GCD pairs: Storing every (start, end) pair instead of grouping by GCD value blows up memory.
• Ignoring single-element subarrays: Large elements with large GCDs (themselves) can dominate the answer.

Interview preparation tip

For the Array Math Number Theory Binary Search interview pattern, practice the "distinct GCDs ending at index i" technique separately before combining it with sum optimization. Understand that GCD is monotone non-increasing as you extend a subarray left — this is the key property enabling efficient enumeration.