Q1、數組的最大因子得分

1、題目描述

給你一個整數數組 nums。

因子得分 定義為數組所有元素的最小公倍數（LCM）與最大公約數（GCD）的 乘積。

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

注意，單個數字的 LCM 和 GCD 都是其本身，而 空數組 的因子得分為 0。

2、解題思路

為了解決這個問題，我們將使用 前綴和后綴數組 的方法，動態計算移除每個元素后的因子得分。

1. 數學性質

   1. 單個數字的 GCD 和 LCM：

      • 對于單個數字 x，其 GCD 和 LCM 都是 x，因此因子得分為 $x\times x=x^2$。

   2. 空數組的 GCD 和 LCM：

      • 空數組的 GCD 和 LCM 均為 0，因此因子得分為 0。

   3. GCD 和 LCM 的計算公式：

      • 最大公約數（GCD）：gcd(a, b)。

      • 最小公倍數（LCM）：lcm(a, b) = a / gcd(a, b) * b。

2. 前綴和后綴數組

   為了高效地計算移除每個元素后的 GCD 和 LCM，我們使用前綴和后綴數組：

   1. 后綴數組：
      • sufGCD[i] 表示從索引 i 到數組末尾所有元素的 GCD。
      • sufLCM[i] 表示從索引 i 到數組末尾所有元素的 LCM。
   2. 前綴變量：
      • preGCD 表示從數組開頭到當前索引的 GCD。
      • preLCM 表示從數組開頭到當前索引的 LCM。

   利用前綴和后綴信息，我們可以在 O(1) 的時間內計算移除某個元素后的剩余數組的 GCD 和 LCM。

3. 動態更新因子得分

• 對于每個索引 i：

  1. 計算移除元素 nums[i] 后，剩余數組的 GCD 和 LCM：

     ? $\text{remainingGCD} = \text{gcd(preGCD, sufGCD[i + 1])} $

     ? $\text{remainingLCM}=\text{lcm(preLCM,?sufLCM[i?+?1])}$

  2. 更新最大因子得分：

     ? $\text{maxFactorScore}=\max (\text{maxFactorScore},\text{remainingGCD}\times \text{remainingLCM})$

  3. 更新前綴 GCD 和前綴 LCM。

3、代碼實現

class Solution {
public:long long maxScore(vector<int>& nums) {int n = nums.size();// 后綴數組:// sufGCD[i] 表示從索引 i 到末尾所有元素的 GCD// sufLCM[i] 表示從索引 i 到末尾所有元素的 LCMvector<int> sufGCD(n + 1, 0);       // 初始化為 0, 表示 GCDvector<long long> sufLCM(n + 1, 1); // 初始化為 1, 表示 LCM// 計算后綴 GCD 和后綴 LCMfor (int i = n - 1; i >= 0; i--) {sufGCD[i] = gcd(sufGCD[i + 1], nums[i]);sufLCM[i] = lcm(sufLCM[i + 1], nums[i]);}// 初始答案: 不移除任何元素時的因子得分long long maxFactorScore = static_cast<long long>(sufGCD[0]) * sufLCM[0];// 前綴變量: preGCD 和 preLCMint preGCD = 0;       // 前綴 GCD, 初始為 0long long preLCM = 1; // 前綴 LCM, 初始為 1// 枚舉每個元素作為移除目標for (int i = 0; i < n; i++) {// 移除 nums[i] 后, 剩余部分的 GCD 和 LCMint remainingGCD = gcd(preGCD, sufGCD[i + 1]);long long remainingLCM = lcm(preLCM, sufLCM[i + 1]);// 更新最大因子得分maxFactorScore = max(maxFactorScore, static_cast<long long>(remainingGCD) * remainingLCM);// 更新前綴 GCD 和前綴 LCMpreGCD = gcd(preGCD, nums[i]);preLCM = lcm(preLCM, nums[i]);}return maxFactorScore;}
};

4、復雜度分析

1. 時間復雜度：

   • 后綴數組計算需要 O(n)。

   • 遍歷每個元素更新前綴和計算剩余數組的 GCD 和 LCM，也需要 O(n)。

   • 總體復雜度為 O(n)。

2. 空間復雜度：

   • 使用了 sufGCD 和 sufLCM 兩個數組，空間復雜度為 O(n)。