LeetCode 题解工作台
数组的最大因子得分
给你一个整数数组 nums 。 因子得分 定义为数组所有元素的最小公倍数（LCM）与最大公约数（GCD）的 乘积 。 在 最多 移除一个元素的情况下，返回 nums 的 最大因子得分 。 注意 ，单个数字的 LCM 和 GCD 都是其本身，而 空数组 的因子得分为 0。 示例 1： 输入： nums…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·数学
答案摘要
class Solution: def maxScore(self, nums: List[int]) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·数学 题型思路
题目描述
给你一个整数数组 nums。
因子得分 定义为数组所有元素的最小公倍数（LCM）与最大公约数（GCD）的 乘积。
在 最多 移除一个元素的情况下，返回 nums 的 最大因子得分。
注意，单个数字的 LCM 和 GCD 都是其本身，而 空数组 的因子得分为 0。
示例 1：
输入： nums = [2,4,8,16]
输出： 64
解释：
移除数字 2 后，剩余元素的 GCD 为 4，LCM 为 16，因此最大因子得分为 4 * 16 = 64。
示例 2：
输入： nums = [1,2,3,4,5]
输出： 60
解释：
无需移除任何元素即可获得最大因子得分 60。
示例 3：
输入： nums = [3]
输出： 9
提示：
1 <= nums.length <= 1001 <= nums[i] <= 30
解题思路
方法一
class Solution:
def maxScore(self, nums: List[int]) -> int:
n = len(nums)
suf_gcd = [0] * (n + 1)
suf_lcm = [0] * n + [1]
for i in range(n - 1, -1, -1):
suf_gcd[i] = gcd(suf_gcd[i + 1], nums[i])
suf_lcm[i] = lcm(suf_lcm[i + 1], nums[i])
ans = suf_gcd[0] * suf_lcm[0]
pre_gcd, pre_lcm = 0, 1
for i, x in enumerate(nums):
ans = max(ans, gcd(pre_gcd, suf_gcd[i + 1]) * lcm(pre_lcm, suf_lcm[i + 1]))
pre_gcd = gcd(pre_gcd, x)
pre_lcm = lcm(pre_lcm, x)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on computing LCM and GCD for each removal, roughly O(n^2) with naive methods. Space complexity is O(n) if prefix and suffix arrays are used for optimization. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Are you accounting for the no-removal case explicitly?
- question_mark
How are you computing LCM efficiently for multiple elements?
- question_mark
What happens when the array has a single element?
常见陷阱
外企场景- error
Forgetting to consider the original array without removing any element.
- error
Miscomputing LCM or GCD for more than two numbers.
- error
Ignoring small arrays where removing an element is not possible or unnecessary.
进阶变体
外企场景- arrow_right_alt
Maximize sum of LCM and GCD instead of product.
- arrow_right_alt
Allow removing up to two elements to maximize factor score.
- arrow_right_alt
Apply the same problem on a multi-dimensional array.