2.9　最大整除子集

题目描述（第368题）

给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对(Si,Sj)都要满足Si % Sj=0或Sj % Si =0。

如果有多个目标子集，返回其中任何一个均可。

示例1

输入：[1,2,3]

输出：[1,2]（当然，[1,3]也正确）

示例2

输入：[1,2,4,8]

输出：[1,2,4,8]

思路

符合直觉的想法是求出所有的子集，一共是2n个，然后判断是否满足“整除子集”的条件，并最终取出最大的即可，但这样做的复杂度非常高，我们来思考如何优化。

首先明确一点：如果存在一个整除子集S及整数x，x能够被S中最大的数整除，那么将x加入S就可以组成一个更大的整除子集。这个其实就是递推公式，因此可以维护一个集合，集合的key是整除子集中最大的数，value是整除子集S本身。具体算法如下。

●　对数组进行排序，这里不妨进行一次升序排序。

●　遍历元素，对于数组中的每一项x，检查x能否被S中的每一项S[d]整除，也就是检查x % d是否等于0。

●　如果可以，则说明最大整除子集可以+1，我们找到的新的最大整除子集为S[d]+x。如果不可以，什么都不需要做。

●　当S全部遍历完成时，我们找出S[d]+x中的最大者，将其写回S[x]。

●　最后取S集合中的长度最大值即可。

代码

如果你喜欢短小精悍的代码，可以参考下面这段代码。

复杂度分析

●　时间复杂度：由于S会在循环的过程逐渐增大，最大会增大到n，因此时间复杂度为O(n2)，其中n为数组长度。

●　空间复杂度：我们使用的额外空间有S和temp，其中temp长度最大为n，而S中的key共有n+1个，value为一个set，set的平均长度为n，因此总的空间复杂度为O(n2)，其中n为数组长度。