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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution {
public long gcd(long a, long b) {
if (b == 0) return a;
return gcd(b, a % b);
}
public long lcm(long a, long b) {
return a * b / gcd(a, b);
}
public long maxScore(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
long[] preGcd = new long[n + 1];
long[] preLcm = new long[n + 1];
long[] sufGcd = new long[n + 1];
long[] sufLcm = new long[n + 1];
preLcm[0] = 1;
for (int i = 0; i < n; i++) {
preGcd[i + 1] = gcd(preGcd[i], nums[i]);
preLcm[i + 1] = lcm(preLcm[i], nums[i]);
}
sufLcm[n] = 1;
for (int i = n - 1; i >= 0; i--) {
sufGcd[i] = gcd(sufGcd[i + 1], nums[i]);
sufLcm[i] = lcm(sufLcm[i + 1], nums[i]);
}
long res = preGcd[n] * preLcm[n];
for (int i = 0; i < n; i++) {
long g = gcd(preGcd[i], sufGcd[i+1]);
long l = lcm(preLcm[i], sufLcm[i+1]);
res = Math.max(res, g*l);
}
return res;
}
}
|
