Largest subset such that for every two elements one of them divides the other

Question

So the problem states:

An array of $N (1 \leq N \leq 2000)$ natural numbers is given. Find the cardinality of the largest subset of that array such that for every two numbers $A$ and $B$ either $A|B$ or $B|A$ (or both).

I know you don't like it when people post questions without trying anything, but the only thing I can possibly think of (that would work) is brute force, which would mean exploring every possible subset and then checking the given condition, again, by brute force.

But since the time complexity of subset exploration is $O(2^N)$, and $N = 2000$ in the worst case, this solution becomes pretty useless.

Other thing I had in mind was some kind of divide and conquer algorithm, similar to merge-sort. But I can't think of a way I'd use the results of two (left and right) subarrays to compute the result for their union.

So, any ideas?

Thanks.

EDIT: The brute force solution I've made that seems to be working (C++):

int largestSubset(const vector<int>&arr, int i, vector<int>&subset, int j){
    if(i == arr.size()){
        //brute force check
        for(int k = 0; k < j; k++){
            for(int s = k + 1; s < j; s++){
                if ((subset[k] % subset[s] != 0) && (subset[s] % subset[k] != 0)){
                    return 0;
                }
            }
        }
        return j;
    }

    //skip the i-th element
    int count1 = largestSubset(arr, i+1, subset, j);
    //include the i-th element
    subset[j] = arr[i];
    int count2 = largestSubset(arr, i+1, subset, j+1);


    return  max(count1, count2);

}

Answer 1

You can do it in $O(N^2)$ like that:

First, sort your array $L$ in increasing order.

Then, for $i \in \{0,\ldots,N-1\}$, let $M[i]$ denote the cardinality of the largest valid subset $S$ such that $L[i]$ is the largest element of $S$.

We can compute $M[i]$ in a dynamic programming fashion: $$ M[0] = 1$$ $$\forall i \;\; s.t.\;\; 0<i<N-1: M[i] = 1 + \max_{0\leq j < i\\L[j]\ |\ L[i]}\{M[j]\}$$ (where the max is taken to be equal to $0$ if no $L[j]$ divides $L[i]$)

To see that, notice that it is clear that $M[i] \leq 1 + \max_{0\leq j < i\\L[j]\ |\ L[i]}\{M[j]\}$ as the second largest element in the corresponding subset must divide $L[i]$. Moreover, the fact that the second largest element $L[j]$ divides $L[i]$ and that the subset without $L[i]$ is valid is enough to guarantee that the subset with $L[i]$ is valid, as all elements in the subset are compatible between them and all divide $L[j]$ and thus divide $L[i]$. Thus the dynamic programming formulation is correct.

Then, the value you are looking for is simply the maximum over all $M[i]$'s.

This leads directly to a $O(N^2)$ algorithm as the sorting can be done in $O(N\log(N))$, and finding the maximum in $M$ is done in $O(N)$.