1. 解题思路
这一题是基于deepseek的实现上面搞定的，虽然deepseek事实上也是超时……
我的直接思路就是动态规划，但是那样是会直接超时的，而deepseek的解决方式是首先找出所有可能的最大公约数，然后考察其对应的score，最后取出其中的最大值。
但是deepseek的解答还是超时了，原因在于其要对每一个数找出其所有的约数，由于数字最大可以到 10 9 10^9 109，因此单个数的查找会非常耗时，我们也就是在这里做了一下优化，具体来说就是直接二重遍历一下所有的区间内的最大公约数，而不是考察每一个数的约数。
如此修改之后，代码勉强通过了全部测试样例，也是挺坑的……
2. 代码实现
给出python代码实现如下：
def get_primes(n):
primes = set()
status = [0 for _ in range(n+1)]
for i in range(2, n+1):
if status[i] == 1:
continue
primes.add(i)
for j in range(i, n+1, i):
status[j] = 1
return primes
PRIMES = get_primes(10**5)
class Solution:
def maxGCDScore(self, nums: List[int], k: int) -> int:
n = len(nums)
if len(set(nums)) == 1:
return max(n * nums[0], min(n, k) * 2 * nums[0])
divisors = set()
for i in range(n):
_gcd = 2*nums[i]
divisors.add(nums[i])
divisors.add(_gcd)
if _gcd in divisors and _gcd in PRIMES:
continue
for j in range(i+1, n):
_gcd = gcd(_gcd, 2*nums[j])
divisors.add(_gcd)
if _gcd == 1 or _gcd in PRIMES:
break
ans = 0
divisors = sorted(divisors, reverse=True)
for div in divisors:
if div * n <= ans:
break
op, cnt = 0, 0
for i, num in enumerate(nums):
if div * (n-i+cnt) <= ans:
break
if num % div == 0:
pass
elif (num * 2) % div == 0:
op += 1
else:
op, cnt = 0, 0
continue
cnt += 1
while cnt > 0 and op > k:
li = i - cnt + 1
if nums[li] % div != 0:
op -= 1
cnt -= 1
ans = max(ans, cnt * div)
return ans
提交代码评测得到：耗时13858ms，占用内存19.2MB。