Maximize Subarray GCD Score
You are given an array of positive integers nums and an integer k.
You may perform at most k operations. In each operation, you can choose one element in the array and double its value. Each element can be doubled at most once.
The score of a contiguous subarray is defined as the product of its length and the greatest common divisor (GCD) of all its elements.
Return the maximum score that can be achieved by selecting a contiguous subarray from the modified array.
Note:
- The greatest common divisor (
GCD) of an array is the largest integer that evenly divides all the array elements.
Example 1
Input
nums = [2,4], k = 1Output
8Double nums[0] to 4, making the array [4, 4], whose full subarray has GCD 4 and length 2 for a score of 8.
Example 2
Input
nums = [3,5,7], k = 2Output
14Double nums[2] to 14, making the best subarray [14] with GCD 14 and length 1 for a score of 14.
Constraints
- 1 <= n == nums.length <= 1500
- 1 <= nums[i] <= 10^9
- 1 <= k <= n