Largest Divisible Subset
Application of Longest Increasing Subsequence

Customer Support: admin@thealgorists.com

Feedback:
We are listening to your every feedback,
and taking action to constantly improve your learning experience.
If you have any feedback, please use this form:
https://thealgorists.com/Feedback.
 If you are a student, email to admin@thealgorists.com to get special student discount.
Problem Statement:
Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this subset satisfies:
Si % Sj = 0 or Sj % Si = 0.
If there are multiple solutions, return any subset is fine.
Example 1:
Input: [1,2,3]
Output: [1,2] (of course, [1,3] will also be ok)
Example 2:
Input: [1,2,4,8]
Output: [1,2,4,8]
Solution:

Recall from Longest Increasing Subsequence
chapter that
most problems where
you are given an array (or list) of items and you'd have to find the largest subset of the items which maintains certain given condition
could be solved using Longest Increasing Subsequence technique.
The below two observations would help us to come up with our algorithm to solve this problem:

Given a list of values [E, F, G] sorted in ascending order (i.e. E < F < G),
and the list itself forms a divisible subset as described in the problem,
then we could extend the subset without enumerating all numbers in the subset, in the following two cases:

For any value that can be divided by the largest element in the divisible subset,
by adding the new value into the subset, one can form another divisible subset, i.e. for all h,
if h % G == 0, then [E, F, G, h] forms a new divisible subset.
Example: [2, 4, 8] is a divisible list. Now 40 % 8 = 0, and the list [2, 4, 8, 40] is also divisible. 
For all value that can divide the smallest element in the subset, by adding the new value into the subset, one can form another divisible subset, i.e. for all d, if E % d == 0, then [d, E, F, G] forms a new divisible subset.
Example: [4, 8, 16] is a divisible list. Now 2 % 4 = 0, and the list [2, 4, 8, 16] is also divisible.

For any value that can be divided by the largest element in the divisible subset,
by adding the new value into the subset, one can form another divisible subset, i.e. for all h,
if h % G == 0, then [E, F, G, h] forms a new divisible subset.
We sort the given integer array in ascending sort. Now the Longest Increasing Subsequence of the sorted array maintaining the given divisibility condition would give us the largest divisible subset, as shown in code below.
Code:
This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.
Other related chapters:
 Core Concept
 Box Stacking
 Russian Doll Envelopes
 Longest String Chain
 Best Team with No Conflict
 Longest Bitonic Subsequence
The above content is written by:
Abhishek Dey
A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More
Microsoft  University of Florida
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn