# Largest Divisible Subset

<https://leetcode.com/problems/largest-divisible-subset/description/>

> Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies: Si % Sj = 0 or Sj % Si = 0.
>
> If there are multiple solutions, return any subset is fine.

## Thoughts

如果这道题只是问最长的能互相除的子序列是什么，会简洁很多，思路和LIS相似。让f\[i]表示以i为尾的互除子序列，f\[i]初始值为1，因为它能除自身。然后遍历所有已经遍历过了的看nums\[i]是否能整除nums\[j], 如果可以整除则把f\[j] + 1和现有f\[i]比较取最大值。这题比较麻烦的是不但让你返回最大长度，还要求返回完整的序列。因此我们用一个array记录下对于f\[i]找到的最大的j。然后就能从尾往前回溯得到目标序列了。

## Code

```
class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        int n = nums.length, max = 0, maxIndex = 0;
        int[] f = new int[n], pres = new int[n];
        List<Integer> res = new ArrayList<>();
        if (n == 0) {
            return res;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            f[i] = 1;
            pres[i] = i;
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0 && f[j] + 1 > f[i]) {
                    pres[i] = j; 
                    f[i] = f[j] + 1;
                }
            }
            if (f[i] > max) {
                max = f[i];
                maxIndex = i;
            }
        }

        while (pres[maxIndex] != maxIndex) {
            res.add(nums[maxIndex]);
            maxIndex = pres[maxIndex];
        }
        res.add(nums[maxIndex]);
        return res;
    }
}
```

## Analysis

Errors:

1. max = f\[i];忘了写
2. res.add(nums\[subres])写在了map.get后
3. 没有排序

做题耗时50min

时间复杂度O(n^2).


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/fidai-biao-yiinput-i-wei-jie-wei-de-zhi/largest-divisible-subset.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.