Largest Divisible Subset
DP on LIS DSA practice problem on Onlearn.
Difficulty: hard.
Topics: Finding the Longest Divisible Subset in an Array, Dynamic Programming, Subsequences, Sorting, Arrays, Time Complexity, Space Complexity, Longest Increasing Subsequence, dynamic programming, sorting algorithms, hashing, combinatorics, time complexity analysis, number theory, Longest Increasing Subsequence (LIS).
Given an array of n distinct positive integers, find the longest subset such that for any pair of elements (Si, Sj) in this subset, either Si % Sj == 0 or Sj % Si == 0. If there are multiple such subsets, return any one. Input Specification: The input consists of a single line containing space separated integers representing the elements of the array. Output Specification: Print the elements of the longest divisible subset, separated by spaces. The elements should be printed in ascending order. Sample Input: 1 16 7 8 4 Sample Output: 1 4 8 16