2025-05-23:数组的最大因子得分。用go语言,给定一个整数数组 nums。
定义“因子得分”为该数组中所有元素的最小公倍数(LCM)与最大公约数(GCD)相乘后的结果。
现在你最多可以移除数组中的一个元素,求在这种情况下,nums 的最大因子得分。
特别说明:
1 <= nums.length <= 100。
1 <= nums[i] <= 30。
输入: nums = [2,4,8,16]。
输出: 64。
解释:
移除数字 2 后,剩余元素的 GCD 为 4,LCM 为 16,因此最大因子得分为 4 * 16 = 64。
题目来自力扣3334。
sufGcd
):sufGcd[i]
表示从 nums[i]
到 nums[n-1]
的 GCD。sufLcm
):sufLcm[i]
表示从 nums[i]
到 nums[n-1]
的 LCM。nums
来计算。sufGcd[0]
(即整个数组的 GCD)。sufLcm[0]
(即整个数组的 LCM)。sufGcd[0] * sufLcm[0]
。nums[i]
,剩余数组是 nums[0..i-1]
和 nums[i+1..n-1]
。gcd(prefixGcd, sufGcd[i+1])
,其中 prefixGcd
是 nums[0..i-1]
的 GCD。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
。n
。sufGcd
和 sufLcm
数组,大小为 n+1
。sufGcd[n] = 0
(因为 gcd(0, x) = x
),sufLcm[n] = 1
(因为 lcm(1, x) = x
)。nums
:sufGcd[i] = gcd(sufGcd[i+1], nums[i])
。sufLcm[i] = lcm(sufLcm[i+1], nums[i])
。ans = sufGcd[0] * sufLcm[0]
。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])
。ans
。sufGcd
和 sufLcm
:O(n),因为每个元素处理一次,每次处理调用 gcd
和 lcm
(可以视为 O(1) 因为数字很小)。gcd
和 lcm
。sufGcd
和 sufLcm
数组:O(n)。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)
}
fn gcd(mut a: i64, mut b: i64) ->i64 {
while a != 0 {
lettemp = a;
a = b % a;
b = temp;
}
b
}
fnlcm(a: i64, b: i64) ->i64 {
a / gcd(a, b) * b
}
fnmax_score(nums: &[i64]) ->i64 {
letn = nums.len();
letmut suf_gcd = vec![0; n + 1];
letmut suf_lcm = vec![1; n + 1];
// 从后往前计算后缀的gcd和lcm
foriin (0..n).rev() {
suf_gcd[i] = gcd(suf_gcd[i + 1], nums[i]);
suf_lcm[i] = lcm(suf_lcm[i + 1], nums[i]);
}
// 不移除元素的情况
letmut ans = suf_gcd[0] * suf_lcm[0];
letmut pre_gcd = 0;
letmut pre_lcm = 1;
foriin0..n {
// 移除 nums[i]
letcurr = 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
}
fnmain() {
letnums = vec![2, 4, 8, 16];
letresult = max_score(&nums);
println!("{}", result);
}