这是 LeetCode 3574. 最大子数组 GCD 分数 的 Python3 实现。解题思路核心观察翻倍操作最多只能让子数组的 GCD 乘以 2。因此对于每个子数组我们需要判断是否能通过最多 k 次翻倍操作使 GCD 翻倍。关键步骤1. 预处理统计每个数中因子 2 的个数即 x 能被 2 整除的次数2. 枚举子数组固定左端点 l向右扩展右端点 r3. 维护三个值- g当前子数组的 GCD- mi子数组中因子 2 个数的最小值- t具有最小因子 2 个数的元素个数4. 判断翻倍如果 t k说明需要翻倍的元素超过 k 个无法翻倍否则 GCD 可以翻倍时间复杂度O(n^2 \cdot \log n)空间复杂度O(n)Python3 代码pythonfrom math import gcdfrom typing import Listclass Solution:def maxGCDScore(self, nums: List[int], k: int) - int:n len(nums)# 预处理统计每个数中因子 2 的个数cnt [0] * nfor i, x in enumerate(nums):while x % 2 0:cnt[i] 1x // 2ans 0# 枚举所有子数组for l in range(n):g 0 # 当前子数组 GCDmi float(inf) # 最小因子 2 个数t 0 # 具有最小因子 2 个数的元素个数for r in range(l, n):# 更新 GCDg gcd(g, nums[r])# 更新最小因子 2 个数及其出现次数if cnt[r] mi:mi cnt[r]t 1elif cnt[r] mi:t 1# 判断是否能翻倍 GCD# 如果具有最小因子 2 个数的元素个数 k则无法翻倍val g if t k else g * 2length r - l 1ans max(ans, val * length)return ans代码说明- cnt[i] 记录 nums[i] 中因子 2 的个数例如 12 2^2 × 3则 cnt[i] 2- 翻倍操作的本质是将某个数乘以 2相当于增加一个因子 2- 子数组 GCD 中因子 2 的个数取决于子数组中所有数因子 2 个数的最小值 mi- 如果具有最小值 mi 的元素个数 t k则最多 k 次翻倍无法让所有这些元素的因子 2 个数都增加GCD 无法翻倍- 否则可以通过翻倍使 GCD 乘以 2这个解法在 n \le 1500 的约束下可以通过所有测试用例。