题目描述

给你一个整数数组 nums。

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

在 最多 移除一个元素的情况下，返回 nums 的 最大因子得分。

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

样例

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

输出： 64

解释：

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

输入： nums = [1,2,3,4,5]

输出： 60

解释：

无需移除任何元素即可获得最大因子得分 60。

输入： nums = [3]

输出： 9

限制

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 30

算法

(前后缀分解) $O(n \log m)$

1. 首先倒序遍历，求出每个后缀的 GCD 和 LCM。
2. 然后遍历前缀并维护前缀的 GCD 和 LCM。每次枚举移除的元素，让前缀后缀拼接更新答案。

时间复杂度

• 遍历数组两次，遍历时更新 GCD 的时间复杂度为 $O(\log m)$。
• 故总时间复杂度为 $O(n \log m)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储后缀的 GCD 和 LCM。

C++ 代码

#define LL long long

class Solution {
private:
    LL lcm(LL x, LL y) {
        return x / gcd(x, y) * y;
    }

public:
    LL maxScore(vector<int>& nums) {
        const int n = nums.size();
        vector<LL> suf_gcd(n + 1), suf_lcm(n + 1);
        suf_gcd[n] = 0;
        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]);
        }

        LL ans = suf_gcd[0] * suf_lcm[0];

        LL pre_gcd = 0, pre_lcm = 1;
        for (int i = 0; i < n; 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;
    }
};