class Solution {
public:
long long maxScore(vector<int>& nums) {
}
};
3334. 数组的最大因子得分
给你一个整数数组 nums。
因子得分 定义为数组所有元素的最小公倍数（LCM）与最大公约数（GCD）的 乘积。
在 最多 移除一个元素的情况下，返回 nums 的 最大因子得分。
注意，单个数字的 LCM 和 GCD 都是其本身，而 空数组 的因子得分为 0。
lcm(a, b) 表示 a 和 b 的 最小公倍数。
gcd(a, b) 表示 a 和 b 的 最大公约数。
示例 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原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 4.2 MB, 提交时间: 2024-11-08 22:06:37
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)
}
return int64(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
}
cpp 解法, 执行用时: 7 ms, 内存消耗: 25.6 MB, 提交时间: 2024-11-08 22:06:19
class Solution {
public:
long long maxScore(vector<int>& nums) {
int n = nums.size();
vector<int> suf_gcd(n + 1);
vector<long long> suf_lcm(n + 1);
suf_lcm[n] = 1;
for (int i = n - 1; i >= 0; i--) {
suf_gcd[i] = gcd(suf_gcd[i + 1], nums[i]);
suf_lcm[i] = lcm(suf_lcm[i + 1], nums[i]);
}
long long ans = suf_gcd[0] * suf_lcm[0]; // 不移除元素
int pre_gcd = 0;
long long pre_lcm = 1;
for (int i = 0; i < n; i++) { // 枚举移除 nums[i]
ans = max(ans, gcd(pre_gcd, suf_gcd[i + 1]) * lcm(pre_lcm, suf_lcm[i + 1]));
pre_gcd = gcd(pre_gcd, nums[i]);
pre_lcm = lcm(pre_lcm, nums[i]);
}
return ans;
}
};
java 解法, 执行用时: 2 ms, 内存消耗: 41.9 MB, 提交时间: 2024-11-08 22:05:54
class Solution {
public long maxScore(int[] nums) {
int n = nums.length;
int[] sufGcd = new int[n + 1];
long[] sufLcm = new long[n + 1];
sufLcm[n] = 1;
for (int i = n - 1; i >= 0; i--) {
sufGcd[i] = (int) gcd(sufGcd[i + 1], nums[i]);
sufLcm[i] = lcm(sufLcm[i + 1], nums[i]);
}
long ans = sufGcd[0] * sufLcm[0]; // 不移除元素
int preGcd = 0;
long preLcm = 1;
for (int i = 0; i < n; i++) { // 枚举移除 nums[i]
ans = Math.max(ans, gcd(preGcd, sufGcd[i + 1]) * lcm(preLcm, sufLcm[i + 1]));
preGcd = (int) gcd(preGcd, nums[i]);
preLcm = lcm(preLcm, nums[i]);
}
return ans;
}
private long gcd(long a, long b) {
while (a != 0) {
long tmp = a;
a = b % a;
b = tmp;
}
return b;
}
private long lcm(long a, long b) {
return a / gcd(a, b) * b;
}
}
python3 解法, 执行用时: 3 ms, 内存消耗: 16.7 MB, 提交时间: 2024-11-08 22:05: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): # 枚举移除 nums[i]
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