Is Maximum GCD-Sum of a Subarray easy or hard?

Maximum GCD-Sum of a Subarray is considered a Hard problem. The difficulty comes from combining multiple concepts: subarray enumeration, efficient GCD updates, and prefix sums. Recognizing that subarray GCD values collapse into a small set is the key insight.

Maximum GCD-Sum of a Subarray Python/Java solution

Python, Java, C++, Go, and TypeScript implementations all follow the same pattern: compute prefix sums, maintain a list of current GCD states, update them using gcd(prev, nums[i]), merge duplicates, and evaluate gcd * subarray sum. The complexity remains O(n log V) regardless of language.

How to solve Maximum GCD-Sum of a Subarray in O(n)?

Strict O(n) is difficult because every extension of a subarray requires a GCD operation. The closest practical complexity is O(n log V) using GCD compression. By merging identical GCD states for subarrays ending at each index, the algorithm keeps only a small number of candidates and processes the array nearly linearly.

What is the best approach for Maximum GCD-Sum of a Subarray?

The most efficient approach uses prefix sums combined with GCD compression. For every index, track all distinct GCD values of subarrays ending at that position and merge duplicates. This limits the number of states to about O(log V). The overall complexity becomes O(n log V), which works well for large arrays.

Is Maximum GCD-Sum of a Subarray asked at Google/Amazon/Meta?

Problems involving subarray GCDs and prefix sums appear in interviews at companies like Google, Amazon, and Meta. While this exact problem may not appear verbatim, the technique of maintaining compressed GCD states for subarrays is a known interview pattern in number theory and array optimization questions.

What data structure is used in Maximum GCD-Sum of a Subarray?

The solution typically uses arrays or lists to store compressed GCD states and a prefix sum array for fast range sum queries. Each state represents a pair of (gcd value, start index). These states are updated iteratively while scanning the array.

What is the time complexity of Maximum GCD-Sum of a Subarray?

The optimal solution runs in O(n log V) time, where n is the array length and V is the maximum value in the array. Each index generates a small set of distinct GCD states and each update requires a gcd computation that costs O(log V). Space complexity is typically O(log V).

2941. Maximum GCD-Sum of a Subarray - Practice Online

You are given an array of integers nums and an integer k.

The gcd-sum of an array a is calculated as follows:

Let s be the sum of all the elements of a.
Let g be the greatest common divisor of all the elements of a.
The gcd-sum of a is equal to s * g.

Return the maximum gcd-sum of a subarray of nums with at least k elements.

Example 1:

Input: nums = [2,1,4,4,4,2], k = 2
Output: 48
Explanation: We take the subarray [4,4,4], the gcd-sum of this array is 4 * (4 + 4 + 4) = 48.
It can be shown that we can not select any other subarray with a gcd-sum greater than 48.

Example 2:

Input: nums = [7,3,9,4], k = 1
Output: 81
Explanation: We take the subarray [9], the gcd-sum of this array is 9 * 9 = 81.
It can be shown that we can not select any other subarray with a gcd-sum greater than 81.

Constraints:

n == nums.length
1 <= n <= 10⁵
1 <= nums[i] <= 10⁶
1 <= k <= n