难度: Hard
Submission
运行时间: 1219 ms
内存: 25.6 MB
class Solution:
def maxGcdSum(self, nums: List[int], k: int) -> int:
l = {}
ans = max(nums) ** 2 if k == 1 else 0
for i, x in enumerate(nums):
r = {x: (x, 1)}
for key, (sum_, length) in l.items():
g = gcd(key, x)
if g not in r:
r[g] = (sum_ + x, length + 1)
else:
if (sum_ + x) > r[g][0]:
r[g] = (sum_ + x, length + 1)
elif (sum_ + x) == r[g][0]:
r[g] = (sum_ + x, max(length + 1, r[g][1]))
if r[g][1] >= k:
ans = max(ans, r[g][0] * g)
l = r
return ans
Explain
此题解采用了动态规划和哈希表的混合策略来解决问题。基本思路是通过遍历数组，持续更新以每个元素为结尾的子数组的最大GCD和其对应的和与长度。使用哈希表来存储当前所有可能的GCD值及其对应的最大和与子数组长度。对于每个新的元素x，更新哈希表，检查与之前每个子数组的最大公约数，并更新这些公约数的最大和与长度。如果达到子数组长度k，计算可能的答案。这种方法确保了我们能够找到长度至少为k的子数组的最大GCD-Sum。
时间复杂度: O(n^2)
空间复杂度: O(n)
class Solution:
def maxGcdSum(self, nums: List[int], k: int) -> int:
l = {} # 存储当前所有可能的GCD及其对应的最大和与子数组长度
# 特殊情况处理，当k为1时，返回最大元素的平方
ans = max(nums) ** 2 if k == 1 else 0
for i, x in enumerate(nums): # 遍历数组中的每个元素
r = {x: (x, 1)} # 初始化当前元素的GCD为其本身
for key, (sum_, length) in l.items(): # 遍历之前的哈希表
g = gcd(key, x) # 计算当前元素与之前GCD的最大公约数
if g not in r: # 如果新的GCD不在哈希表中，初始化
r[g] = (sum_ + x, length + 1)
else: # 如果已存在，尝试更新最大和与最大长度
if (sum_ + x) > r[g][0]:
r[g] = (sum_ + x, length + 1)
elif (sum_ + x) == r[g][0]:
r[g] = (sum_ + x, max(length + 1, r[g][1]))
if r[g][1] >= k: # 如果子数组长度达到k，更新答案
ans = max(ans, r[g][0] * g)
l = r # 更新哈希表
return ans
Explore
当`k`为1时，每个单独的元素都可以视为一个符合条件的子数组，因此我们只需要找到数组中的最大元素。因为题目要求计算最大GCD和的平方，而单个元素的GCD是其本身，所以最大元素的GCD和就是最大元素本身，其平方即为答案。这种情况下不需要进行更复杂的动态规划计算，直接返回最大元素的平方可以大大简化问题并提高算法效率。
在算法中，`gcd`函数用于计算两个数的最大公约数。计算最大公约数的经典算法是欧几里得算法，其时间复杂度非常低，平均情况下是O(log(min(a, b)))。在更新哈希表时，我们需要对每个新元素和已有的每个GCD进行计算，使用高效的`gcd`函数可以确保即使这一步骤在每次迭代中重复多次，总体的计算效率仍然是可接受的。
哈希表中的键是子数组的GCD值。在更新哈希表时，首先计算当前元素与已存在GCD的最大公约数。如果这个GCD值不在哈希表中，我们将创建一个新的键，并初始化其对应的和与子数组长度。如果这个GCD值已存在于哈希表中，我们将比较现有的和与新计算的和，选择较大的和来更新，同时更新对应的子数组长度。这种方法确保了哈希表始终存储了对应GCD的最大和与最大长度，从而在后续步骤中可以更有效地找到可能的最大GCD和。
存储每个GCD对应的最大和与子数组长度的策略，可以在遍历数组时持续追踪和更新每种GCD条件下可能的最优解。这允许算法在后续的遍历中快速比较和选择不同GCD下的最优子数组情况，特别是当需要判断子数组长度是否满足题目条件（例如长度至少为k）时。此外，这种存储方式还可以在达到所需子数组长度时，立即计算出当前GCD与其和的乘积，从而实时更新可能的最大GCD-Sum答案。这有助于降低整体的时间复杂度并提高算法效率。