Watch 10 video solutions for Maximum GCD-Sum of a Subarray, a hard level problem involving Array, Math, Binary Search. This walkthrough by NeetCode has 605,143 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array of integers nums and an integer k.
The gcd-sum of an array a is calculated as follows:
s be the sum of all the elements of a.g be the greatest common divisor of all the elements of a.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.length1 <= n <= 1051 <= nums[i] <= 1061 <= k <= n