arrays - 找到最大的子集，其中任何一对数字中的每个数字都可以被另一个数字整除

Question

给定一个大小为 N 的数组 A。我需要找到最大子集的大小，其中子集中的任何一对元素，其中一个可以被另一个整除。

简而言之，找到最大的子集S，其中∀i,j 其中i ≠ j 和i<|S|和 j<|S| S_i%S_j=0 或 S_j%S_i=0.

问题的界限是:

1. 1≤ N≤ 10^3
2. 1≤ A_i≤ 10^9

示例输入/输出:

数组 4 8 2 3输出为 3

解释:

答案集是 (4,8,2)

集合的大小是3

Answer 1

我假设数组 A 中没有重复项。一种方法(伪代码，假设数组索引从 1 开始):

sort the array A to increasing order
allocate an array B the same length as A
for i in 1 .. N do
    B[i] = 1
    for j in 1 .. i-1 do
        if A[i] % A[j] == 0 then
            B[i] = max(B[i], B[j] + 1)
        endif
    endfor
endfor
return the maximum number in array B as answer.

这在 O(n²) 时间内运行并使用 O(n) 额外空间。它在数组 B 中计算由 A 的元素组成并以特定元素结束的最长除数链的长度。 B 中的总最大值必须是最长的此类链的长度。