找到最大的子集，其中任何一个数字中的每个数字可被另一个数字除尽 [英] Finding largest subset where each number in any pair one number is divisible by the other

问题描述

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

Given an array A of size N. I need to find the size of the Largest Subset in which any pair of elements within the subset, one of them is divisible by the other.

总之，找到最大的子集 S ，其中∀i，j 其中 i≠ j 和 i <| S |并且j 或者 sub>％S _i = 0 。

In short, find largest subset S, where ∀i,j where i ≠ j and i<|S| and j<|S| either S_i%S_j=0 or S_j%S_i=0.

问题的界限是： p>

The bounds for the problem are:

1. 1≤ N&le 10 ^ 3


2. 1≤ A _i ≤ 10 ^ 9

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

示例输入/输出：

数组 4 8 2 3
输出是 3

说明：

答案集是（4,8,2）

answer set is (4,8,2)

集合的大小为3

推荐答案

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

I assume there are no duplicates in the array A. One way to do it (pseudocode, assumes array indices starting at 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 ）额外的空间。
它在数组B中计算由A元素组成并以特定元素结尾的最长除数链的长度。 B中的最大最大值必须是这个链中最长的长度。

This runs in O(n²) time and uses O(n) extra space. It calculates in array B the length of the longest divisor chain consisting of elements of A and ending at the specific element. The overall maximum in B must be the length of the longest such chain.

这篇关于找到最大的子集，其中任何一个数字中的每个数字可被另一个数字除尽的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！