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

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

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

特别说明：

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

1 <= nums.length <= 100。

1 <= nums[i] <= 30。

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

输出： 64。

解释：

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

题目来自力扣3334。

解决思路

1. 1. 理解因子得分：因子得分是数组的 LCM 和 GCD 的乘积。我们需要计算原始数组的因子得分，以及移除每一个可能的元素后的因子得分，然后取最大值。
2. 2. 关键观察：
3. o GCD：移除一个元素后，剩余数组的 GCD 是原数组 GCD（移除的元素可能不是 GCD 的约束）或更大的值。
4. o LCM：移除一个元素后，剩余数组的 LCM 是原数组 LCM（移除的元素可能是 LCM 的关键）或更小的值。
5. o 因此，我们需要高效计算移除每一个元素后的 GCD 和 LCM。
6. 3. 预处理：
7. o 后缀 GCD 数组 (sufGcd)：sufGcd[i] 表示从 nums[i] 到 nums[n-1] 的 GCD。
8. o 后缀 LCM 数组 (sufLcm)：sufLcm[i] 表示从 nums[i] 到 nums[n-1] 的 LCM。
9. o 这两个数组可以通过从后向前遍历 nums 来计算。
10. 4. 计算原始因子得分：
11. o 原始 GCD 是 sufGcd[0]（即整个数组的 GCD）。
12. o 原始 LCM 是 sufLcm[0]（即整个数组的 LCM）。
13. o 原始因子得分是 sufGcd[0] * sufLcm[0]。
14. 5. 枚举移除每一个元素：
15. o 对于移除 nums[i]，剩余数组是 nums[0..i-1] 和 nums[i+1..n-1]。
16. o 剩余数组的 GCD 是 gcd(prefixGcd, sufGcd[i+1])，其中 prefixGcd 是 nums[0..i-1] 的 GCD。
17. o 剩余数组的 LCM 是 lcm(prefixLcm, sufLcm[i+1])，其中 prefixLcm 是 nums[0..i-1] 的 LCM。
18. o 在遍历过程中维护 prefixGcd 和 prefixLcm：
19. o 初始时 prefixGcd = 0（因为 gcd(0, x) = x），prefixLcm = 1（因为 lcm(1, x) = x）。
20. o 遍历到 nums[i] 时，先计算移除 nums[i] 的因子得分，然后更新 prefixGcd 和 prefixLcm。
21. 6. 取最大值：
22. o 比较原始因子得分和所有移除一个元素后的因子得分，取最大值。

详细步骤

1. 1. 初始化：
2. o 计算数组长度 n。
3. o 初始化 sufGcd 和 sufLcm 数组，大小为 n+1。
4. o sufGcd[n] = 0（因为 gcd(0, x) = x），sufLcm[n] = 1（因为 lcm(1, x) = x）。
5. 2. 填充后缀数组：
6. o 从后向前遍历 nums：
7. o sufGcd[i] = gcd(sufGcd[i+1], nums[i])。
8. o sufLcm[i] = lcm(sufLcm[i+1], nums[i])。
9. 3. 计算原始因子得分：
10. o ans = sufGcd[0] * sufLcm[0]。
11. 4. 枚举移除每一个元素：
12. o 初始化 prefixGcd = 0，prefixLcm = 1。
13. o 从左到右遍历 nums：
14. o 对于 nums[i]，计算移除后的 GCD 和 LCM：
15. o currentGcd = gcd(prefixGcd, sufGcd[i+1])。
16. o currentLcm = lcm(prefixLcm, sufLcm[i+1])。
17. o currentScore = currentGcd * currentLcm。
18. o 更新 ans = max(ans, currentScore)。
19. o 更新 prefixGcd 和 prefixLcm：
20. o prefixGcd = gcd(prefixGcd, nums[i])。
21. o prefixLcm = lcm(prefixLcm, nums[i])。
22. 5. 返回结果：
23. o 返回 ans。

时间和空间复杂度

• o 时间复杂度：
• o 填充 sufGcd 和 sufLcm：O(n)，因为每个元素处理一次，每次处理调用 gcd 和 lcm（可以视为 O(1) 因为数字很小）。
• o 枚举移除元素：O(n)，同样每次处理调用 gcd 和 lcm。
• o 总时间复杂度：O(n)。
• o 空间复杂度：
• o sufGcd 和 sufLcm 数组：O(n)。
• o 其他变量：O(1)。
• o 总空间复杂度：O(n)。

Go完整代码如下：

package main

import (
    "fmt"
    "slices"
)

func maxScore(nums []int)int64 {
    n := len(nums)
    sufGcd := make([]int, n+1)
    sufLcm := make([]int, n+1)
    sufLcm[n] = 1
    for 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, 1
    for 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和lcm
    for 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);
}

·

我们相信 Go 语言和算法为普通开发者提供了强有力的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的 Go 语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。

欢迎关注“福大大架构师每日一题”，让 Go 语言和算法助力您的职业发展

·