2025-05-23：数组的最大因子得分用go语言，给定一个整数数组 nu

摘要：理解因子得分：因子得分是数组的 LCM 和 GCD 的乘积。我们需要计算原始数组的因子得分，以及移除每一个可能的元素后的因子得分，然后取最大值。2.关键观察：•GCD：移除一个元素后，剩余数组的 GCD 是原数组 GCD（移除的元素可能不是 GCD 的约束）或

2025-05-23：数组的最大因子得分。用go语言，给定一个整数数组 nums。

定义“因子得分”为该数组中所有元素的最小公倍数（LCM）与最大公约数（GCD）相乘后的结果。

现在你最多可以移除数组中的一个元素，求在这种情况下，nums 的最大因子得分。

特别说明：

• 如果数组只剩一个数字，则其因子得分等于该数字自身。• 如果数组为空，则因子得分为 0。

输入： nums = [2,4,8,16]。

输出： 64。

解释：

移除数字 2 后，剩余元素的 GCD 为 4，LCM 为 16，因此最大因子得分为 4 * 16 = 64。

题目来自力扣3334。

1. 理解因子得分：因子得分是数组的 LCM 和 GCD 的乘积。我们需要计算原始数组的因子得分，以及移除每一个可能的元素后的因子得分，然后取最大值。2. 关键观察：• GCD：移除一个元素后，剩余数组的 GCD 是原数组 GCD（移除的元素可能不是 GCD 的约束）或更大的值。• LCM：移除一个元素后，剩余数组的 LCM 是原数组 LCM（移除的元素可能是 LCM 的关键）或更小的值。• 因此，我们需要高效计算移除每一个元素后的 GCD 和 LCM。3. 预处理：• 后缀 GCD 数组 (sufGcd)：sufGcd[i] 表示从 nums[i] 到 nums[n-1] 的 GCD。• 后缀 LCM 数组 (sufLcm)：sufLcm[i] 表示从 nums[i] 到 nums[n-1] 的 LCM。• 这两个数组可以通过从后向前遍历 nums 来计算。4. 计算原始因子得分：• 原始 GCD 是 sufGcd[0]（即整个数组的 GCD）。• 原始 LCM 是 sufLcm[0]（即整个数组的 LCM）。• 原始因子得分是 sufGcd[0] * sufLcm[0]。5. 枚举移除每一个元素：• 对于移除 nums[i]，剩余数组是 nums[0..i-1] 和 nums[i+1..n-1]。• 剩余数组的 GCD 是 gcd(prefixGcd, sufGcd[i+1])，其中 prefixGcd 是 nums[0..i-1] 的 GCD。• 剩余数组的 LCM 是 lcm(prefixLcm, sufLcm[i+1])，其中 prefixLcm 是 nums[0..i-1] 的 LCM。• 在遍历过程中维护 prefixGcd 和 prefixLcm：• 初始时 prefixGcd = 0（因为 gcd(0, x) = x），prefixLcm = 1（因为 lcm(1, x) = x）。• 遍历到 nums[i] 时，先计算移除 nums[i] 的因子得分，然后更新 prefixGcd 和 prefixLcm。6. 取最大值：• 比较原始因子得分和所有移除一个元素后的因子得分，取最大值。1. 初始化：• 计算数组长度 n。• 初始化 sufGcd 和 sufLcm 数组，大小为 n+1。• sufGcd[n] = 0（因为 gcd(0, x) = x），sufLcm[n] = 1（因为 lcm(1, x) = x）。2. 填充后缀数组：• 从后向前遍历 nums：• sufGcd[i] = gcd(sufGcd[i+1], nums[i])。• sufLcm[i] = lcm(sufLcm[i+1], nums[i])。3. 计算原始因子得分：• ans = sufGcd[0] * sufLcm[0]。4. 枚举移除每一个元素：• 初始化 prefixGcd = 0，prefixLcm = 1。• 从左到右遍历 nums：• 对于 nums[i]，计算移除后的 GCD 和 LCM：• currentGcd = gcd(prefixGcd, sufGcd[i+1])。• currentLcm = lcm(prefixLcm, sufLcm[i+1])。• currentScore = currentGcd * currentLcm。• 更新 ans = max(ans, currentScore)。• 更新 prefixGcd 和 prefixLcm：• prefixGcd = gcd(prefixGcd, nums[i])。• prefixLcm = lcm(prefixLcm, nums[i])。5. 返回结果：• 返回 ans。• 时间复杂度：• 填充 sufGcd 和 sufLcm：O(n)，因为每个元素处理一次，每次处理调用 gcd 和 lcm（可以视为 O(1) 因为数字很小）。• 枚举移除元素：O(n)，同样每次处理调用 gcd 和 lcm。• 总时间复杂度：O(n)。• 空间复杂度：• sufGcd 和 sufLcm 数组：O(n)。• 其他变量：O(1)。• 总空间复杂度：O(n)。package mainimport ("fmt""slices")func maxScore(nums int)int64 {n := len(nums)sufGcd := make(int, n+1)sufLcm := make(int, n+1)sufLcm[n] = 1for i, x := range slices.Backward(nums) {sufGcd[i] = gcd(sufGcd[i+1], x)sufLcm[i] = lcm(sufLcm[i+1], x)}ans := sufGcd[0] * sufLcm[0] // 不移除元素preGcd, preLcm := 0, 1for i, x := range nums { // 枚举移除 nums[i]ans = max(ans, gcd(preGcd, sufGcd[i+1])*lcm(preLcm, sufLcm[i+1]))preGcd = gcd(preGcd, x)preLcm = lcm(preLcm, x)}returnint64(ans)}func gcd(a, b int)int {for a != 0 {a, b = b%a, a}return b}func lcm(a, b int)int {return a / gcd(a, b) * b}func main {nums := int{2,4,8,16}result := maxScore(nums)fmt.Println(result)}

Rust完整代码如下：

fn gcd(mut a: i64, mut b: i64) -> i64 {while a != 0 {let temp = a;a = b % a;b = temp;}b}fn lcm(a: i64, b: i64) -> i64 {a / gcd(a, b) * b}fn max_score(nums: &[i64]) -> i64 {let n = nums.len;let mut suf_gcd = vec![0; n + 1];let mut suf_lcm = vec![1; n + 1];// 从后往前计算后缀的gcd和lcmfor i in (0..n).rev {suf_gcd[i] = gcd(suf_gcd[i + 1], nums[i]);suf_lcm[i] = lcm(suf_lcm[i + 1], nums[i]);}// 不移除元素的情况let mut ans = suf_gcd[0] * suf_lcm[0];let mut pre_gcd = 0;let mut pre_lcm = 1;for i in 0..n {// 移除 nums[i]let curr = gcd(pre_gcd, suf_gcd[i + 1]) * lcm(pre_lcm, suf_lcm[i + 1]);if curr > ans {ans = curr;}pre_gcd = gcd(pre_gcd, nums[i]);pre_lcm = lcm(pre_lcm, nums[i]);}ans}fn main {let nums = vec![2, 4, 8, 16];let result = max_score(&nums);println!("{}", result);}