Medium

题目描述

给你一个整数数组 nums。

数组的因子分数定义为该数组所有元素的最小公倍数（LCM）和最大公约数（GCD）的乘积。

返回从数组中最多移除一个元素后，nums 的最大因子分数。

注意，单个数字的 LCM 和 GCD 都是数字本身，空数组的因子分数为 0。

示例 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 <= 100
  • 1 <= nums[i] <= 30

解题思路

这道题需要找到移除最多一个元素后的最大因子分数。我们有两种主要思路：

思路一：暴力枚举法

遍历所有可能的移除方案（包括不移除任何元素），计算每种情况下剩余元素的 GCD 和 LCM，求出因子分数的最大值。时间复杂度为 O(n²)，但由于数组长度最大为 100，完全可以接受。

思路二：前缀后缀优化

为了避免重复计算，我们可以预计算前缀 GCD/LCM 和后缀 GCD/LCM 数组。这样在计算移除第 i 个元素后的结果时，只需要合并 prefix[i-1] 和 suffix[i+1] 即可。

由于数据规模较小，两种方法都可行。这里采用更直观的暴力枚举法：

  1. 首先计算不移除任何元素的因子分数
  2. 然后枚举移除每个元素，计算剩余元素的因子分数
  3. 返回所有情况中的最大值

需要实现 GCD 和 LCM 的计算函数，其中 LCM(a,b) = a * b / GCD(a,b)。

代码实现

class Solution {
public:
    long long gcd(long long a, long long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    
    long long lcm(long long a, long long b) {
        return a / gcd(a, b) * b;
    }
    
    long long maxScore(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return (long long)nums[0] * nums[0];
        
        long long maxScore = 0;
        
        // Try removing no elements
        long long g = nums[0], l = nums[0];
        for (int i = 1; i < n; i++) {
            g = gcd(g, nums[i]);
            l = lcm(l, nums[i]);
        }
        maxScore = max(maxScore, g * l);
        
        // Try removing each element
        for (int skip = 0; skip < n; skip++) {
            if (n == 1) continue;
            
            long long g = -1, l = -1;
            for (int i = 0; i < n; i++) {
                if (i == skip) continue;
                if (g == -1) {
                    g = l = nums[i];
                } else {
                    g = gcd(g, nums[i]);
                    l = lcm(l, nums[i]);
                }
            }
            maxScore = max(maxScore, g * l);
        }
        
        return maxScore;
    }
};

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        import math
        
        n = len(nums)
        if n == 1:
            return nums[0] * nums[0]
        
        def lcm(a, b):
            return a * b // math.gcd(a, b)
        
        max_score = 0
        
        # Try removing no elements
        g, l = nums[0], nums[0]
        for i in range(1, n):
            g = math.gcd(g, nums[i])
            l = lcm(l, nums[i])
        max_score = max(max_score, g * l)
        
        # Try removing each element
        for skip in range(n):
            remaining = [nums[i] for i in range(n) if i != skip]
            if len(remaining) == 0:
                continue
            
            g, l = remaining[0], remaining[0]
            for i in range(1, len(remaining)):
                g = math.gcd(g, remaining[i])
                l = lcm(l, remaining[i])
            max_score = max(max_score, g * l)
        
        return max_score

public class Solution {
    private long Gcd(long a, long b) {
        return b == 0 ? a : Gcd(b, a % b);
    }
    
    private long Lcm(long a, long b) {
        return a / Gcd(a, b) * b;
    }
    
    public long MaxScore(int[] nums) {
        int n = nums.Length;
        if (n == 1) return (long)nums[0] * nums[0];
        
        long maxScore = 0;
        
        // Try removing no elements
        long g = nums[0], l = nums[0];
        for (int i = 1; i < n; i++) {
            g = Gcd(g, nums[i]);
            l = Lcm(l, nums[i]);
        }
        maxScore = Math.Max(maxScore, g * l);
        
        // Try removing each element
        for (int skip = 0; skip < n; skip++) {
            long currentG = -1, currentL = -1;
            for (int i = 0; i < n; i++) {
                if (i == skip) continue;
                if (currentG == -1) {
                    currentG = currentL = nums[i];
                } else {
                    currentG = Gcd(currentG, nums[i]);
                    currentL = Lcm(currentL, nums[i]);
                }
            }
            if (currentG != -1) {
                maxScore = Math.Max(maxScore, currentG * currentL);
            }
        }
        
        return maxScore;
    }
}

var maxScore = function(nums) {
    function gcd(a, b) {
        while (b !== 0) {
            let temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    
    function lcm(a, b) {
        return (a * b) / gcd(a, b);
    }
    
    function getGCD(arr) {
        if (arr.length === 0) return 0;
        let result = arr[0];
        for (let i = 1; i < arr.length; i++) {
            result = gcd(result, arr[i]);
        }
        return result;
    }
    
    function getLCM(arr) {
        if (arr.length === 0) return 0;
        let result = arr[0];
        for (let i = 1; i < arr.length; i++) {
            result = lcm(result, arr[i]);
        }
        return result;
    }
    
    function getScore(arr) {
        if (arr.length === 0) return 0;
        return getGCD(arr) * getLCM(arr);
    }
    
    let maxScore = getScore(nums);
    
    for (let i = 0; i < nums.length; i++) {
        let newArr = nums.slice(0, i).concat(nums.slice(i + 1));
        maxScore = Math.max(maxScore, getScore(newArr));
    }
    
    return maxScore;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n² log M)n 为数组长度，M 为数组元素最大值，每次 GCD/LCM 计算需要 O(log M)
空间复杂度O(1)只使用常数额外空间

相关题目