🔗 🟡 368. Largest Divisible Subset

tags: `陣列(Array)` `排序(Sorting)` `數學(Math)` `動態規劃(Dynamic Programming)`

題意

給定一組正整數 $nums$ ，請找出並回傳其中最大的整除子集 $answer$ ，使得此子集合中的每對元素 $(answer[i], answer[j])$ 滿足以下條件：

$answer[i] \mod answer[j] = 0$ ，或
$answer[j] \mod answer[i] = 0$

如果存在多個解，返回其中任何一個即可。

約束條件

$1 \leq nums.length \leq 1000$
$1 \leq nums[i] \leq 2 * 10^9$
$nums$ 中的所有整數都是唯一的

思路：數學(Math) + 動態規劃(Dynamic Programming)

為了方便說明，以下將 Largest Divisible Subset 簡稱為 LDS，並將 Divisible Subset 簡稱為 DS。

$a | b$ 表示 $a$ 能整除 $b$ ，即 $b \mod a = 0$

首先引入一個重要的前提：往一個 DS 中加入一個數時，不需檢查所有數

假設一個 DS 為 $\{a, b, c\}$ ，其中 $a < b < c$ ，則只要滿足以下任一條件，即可將 $x$ 加入 LDS

$x | a$ (若 $x < a$ )
$c | x$ (若 $x > c$ )

這是因為整除關係具有遞移性(Transitive Property) ，即若 $a | b$ 且 $b | c$ ，則 $a | c$

為了更好地利用這個性質，可以將陣列由小到大進行排序(Sorting)，如此一來，在我們添加新的數字 $x$ 時，只需要檢查 $c$ 是否能整除 $x$ ( $c | x$ ) 即可。至此便可將此問題轉為 Longest Increasing Subsequence (LIS) 問題

方法一：在 Memoization 中保存答案

這種寫法會使得時間和空間複雜度乘上答案所需的空間，因此不建議使用。

定義 $f[i]$ 表示以 $nums[i]$ 結尾的最大整除子集，則 $f[i]$ 可以初始化為 $[nums[i]]$ ，並有以下狀態轉移：

$f[i] = \displaystyle\max_{j=0}^{i-1} \begin{cases} f[j] + [nums[i]] & \text{if } nums[i] \mod nums[j] = 0 \\ f[i] & \text{otherwise} \end{cases}$

比較子集的方式為按長度比較，在 Python 中使用 f[x] = max(f[x], f[y] + [x], key=len) 即可。

複雜度分析

時間複雜度： $O(\log U \cdot n^2)$ $O (lo g U \cdot n^{2})$ ，其中 $U$ $U$ 為陣列中最大元素
- 最大的 LDS 為 $\{1, 2, 4, 8, 16, \cdots\} = \{2^0, 2^1, 2^2, 2^3, 2^4, \cdots\}$ ，因此所需的空間為 $O(\log U)$
空間複雜度： $O(\log U \cdot n)$

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        nums.sort()
        # f[x] 表示以 x 結尾的 Largest Divisible Subset
        f = {x: [x] for x in nums}
        for i, x in enumerate(nums):
            # 枚舉 x 的前一個數 y = nums[j]，若 y | x，則 ∀u, u ∈ f[y] -> u | x
            for j in range(i):
                if x % nums[j] == 0:
                    f[x] = max(f[x], f[nums[j]] + [x], key=len)
        return max(f.values(), key=len)

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        // f[i] 表示以 nums[i] 結尾的 Largest Divisible Subset
        vector<vector<int>> f(n);
        vector<int> ans;
        for (int i = 0; i < n; i++) {
            f[i].push_back(nums[i]);
            // 枚舉 x = nums[i] 的前一個數 y = nums[j]，若 y | x，則 ∀u, u ∈ f[y] -> u | x
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0) {
                    if (f[i].size() < f[j].size() + 1) {
                        f[i] = f[j];
                        f[i].push_back(nums[i]);
                    }
                }
            }
            // 更新答案
            if (f[i].size() > ans.size()) ans = f[i];
        }
        return ans;
    }
};

方法二：空間優化

方法一雖然能找到正確答案，但它在動態規劃的狀態 $f[i]$ 中儲存了完整的 subset。當 subset 很長時，這會導致大量的空間消耗和列表複製操作，影響效能。實際上，我們只需要保存最大的 LDS 大小，再反推答案即可。

我們不再於 DP 狀態中儲存整個子集。取而代之，定義 $f[i]$ 為：以 $nums[i]$ 結尾的 LDS 的長度，並維護一個變數 $mx$ 表示所有 $f[i]$ 中的最大值。同時，我們需要一個方法來稍後重建實際的子集。

這裡我們需要利用前提中提到的性質，若 $x$ 小於整除集合中的所有元素，則只需要檢查 $x | a$ 即可，其中 $a$ 為整除集合中的最小元素。

由於若 $f[i] = mx$ ，則 $nums[i]$ 必定為 LDS 中的最大元素，因此我們只需要從後向前找到最大的 $nums[i]$ 使得 $nums[i]$ 可以加入答案 $ans$ 中即可。

具體來說，在這個過程中，我們尋找滿足以下條件的 $nums[i]$ ，

$f[i]$ 等於當前的目標長度 $mx$ 。
$ans$ 為空 (表示這是找到的第一個元素，即 LDS 中最大的那個)，或者 $ans$ 中最後一個元素能被 $nums[i]$ 整除 (確保新加入的 $nums[i]$ 滿足 LDS 的條件)。
一旦找到符合條件的 $nums[i]$ ，將它加入 $ans$ 中。
將目標長度 $mx$ 減 1，因為我們已經找到了長度為 $mx$ 的那個元素，接下來要找長度為 $mx-1$ 且能整除剛加入元素的那個元素。
重複此過程，直到 $mx$ 變為 0，此時 $ans$ 列表就包含了從大到小排列的一個最大整除子集。

最後得到的是由大到小排列的 LDS，但由於題目允許返回任意一個解，因此不需要進行反轉。

複雜度分析

時間複雜度： $O(n^2)$
空間複雜度： $O(n)$

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        n = len(nums)
        nums.sort()
        # f[i] 表示以 nums[i] 結尾的 Largest Divisible Subset 大小
        f = [1] * n
        mx = 1
        for i, x in enumerate(nums):
            # 枚舉 x 的前一個數 y = nums[j]，若 y | x，則 ∀u, u ∈ f[y] -> u | x
            for j in range(i):
                if x % nums[j] == 0 and f[i] < f[j] + 1:
                    f[i] = f[j] + 1
            mx = max(mx, f[i])  # 更新最大的 LDS 大小
        # 從後往前找，找到最大的 LDS
        ans = []
        for i in range(n - 1, -1, -1):
            if f[i] == mx and (not ans or ans[-1] % nums[i] == 0):
                ans.append(nums[i])
                mx -= 1
        return ans

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        // f[i] 表示以 nums[i] 結尾的 Largest Divisible Subset 最大長度
        vector<int> f(n, 1);
        int mx = 0;
        for (int i = 0; i < n; i++) {
            // 枚舉 x = nums[i] 的前一個數 y = nums[j]，若 y | x，則 ∀u, u ∈ f[y] -> u | x
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0) f[i] = max(f[i], f[j] + 1);
            }
            mx = max(mx, f[i]);
        }
        // 從後往前找，找到最大的 LDS
        vector<int> ans;
        for (int i = n - 1; i >= 0 && mx > 0; i--) {
            if (f[i] == mx && (ans.empty() || ans.back() % nums[i] == 0)) {
                ans.push_back(nums[i]);
                mx--;
            }
        }
        return ans;
    }
};

寫在最後

PROMPT

masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail, vibrant colors, anime style,

1girl, solo, Ganyu, Ganyu (Genshin Impact), long hair, light blue hair, purple eyes, black-red horns, yellow jacket, white shirt, black skirt, looking at viewer, smile, outdoors, yellow tulips, flower field, sunlight,

The image depicts an anime-style Ganyu from Genshin Impact, but with a different outfit and setting. She is wearing a yellow jacket over a white shirt, black skirt, and is standing in a field of yellow tulips. The sun is shining, creating a warm and inviting atmosphere, and she’s smiling at the viewer.