Java 中数组中最长可整除子集的大小

在给定的输入数组中，任务是找出最长可整除子集的大小。当一个子集中的任意一对元素 (p, q) 满足 p 能整除 q (p % q = 0) 或 q 能整除 p (q % p = 0) 时，该子集被称为可整除子集。

示例 1

输入

int arr[] = {1, 16, 7, 19, 28, 8, 4, 64, 256}

输出 6

解释：考虑子集 {1, 16, 8, 4, 64, 256}。在这个子集中，我们可以形成 15 个（⁶C₂ = 15）元素对。在任意一对元素（由两个元素 p 和 q 组成）中，要么 p % q = 0，要么 q % p = 0。此外，所考虑的子集是满足给定条件的最长子集，其大小为 6。因此，输出为 6。

示例 2

输入

int arr[] = {2, 2, 2, 2, 2, 2, 2}

输出 7

解释：由于输入数组中的所有元素值都相同，因此它们可以完全互相整除。因此，最长子集就是输入数组本身，其大小为 7。因此，输出为 7。

方法：使用递归

简单的方法是生成给定输入数组的所有可能子集，然后根据给定条件检查生成的子集是否有效。如果子集有效，则将其大小与之前计算的、之前计算过的有效子集的最大大小进行比较，并相应地更新答案。所有子集都可以通过排除或包含当前元素来生成。我们将同时生成和验证子集的大小。请看下面的实现。

文件名：LongestDivisibleSubset.java

输出

For the input array: 
1 16 7 19 28 8 4 64 256 
The maximum size of the longest divisible subset is: 6


For the input array: 
2 2 2 2 2 2 2 
The maximum size of the longest divisible subset is: 7

复杂度分析：该程序在每次递归调用中进行两次递归调用。这导致指数级时间复杂度。因此，程序的 time complexity 是 O(2n)。存储所有子集的数组列表（在本例中为 subsetAL）使 space complexity 呈指数级增长，也为 O(2n)，其中 n 是输入数组中存在的总元素数。

上述程序的 time complexity 和 space complexity 都非常高，不适用于较大的输入。因此，需要降低这两种复杂度。

高效方法：使用排序

通过排序，可以降低程序的 time complexity 和 space complexity。请看以下步骤。

步骤 1：将输入数组的所有元素按升序排序。排序的原因是为了确保一个元素的所有除数都出现在它之前。

步骤 2：创建一个大小与输入数组相同的数组 divisibleCount[]。divisibleCount[i] 存储以 arr[i] 结尾的可整除子集的大小（在排序后的数组中）。divisibleCount [i] 的最小值将为 1。

步骤 3：遍历所有数组元素。对于每个元素，找到一个除数 arr[j]，使其 divisibleCount[j] 的值最大，并将 divisibleCount[i] 的值设置为 divisibleCount[j] + 1。

观察上述步骤的实现。

文件名：LongestDivisibleSubset1.java

输出

For the input array: 
1 16 7 19 28 8 4 64 256 
The maximum size of the longest divisible subset is: 6


For the input array: 
2 2 2 2 2 2 2 
The maximum size of the longest divisible subset is: 7

复杂度分析：该程序使用了两个嵌套的 for 循环，这使得程序的 time complexity 为 O(n²)。该程序还使用了辅助数组来查找结果，这使得程序的 space complexity 为 O(n)，其中 n 是输入数组中存在的总元素数。