Variations of LIS

LIS (Longest Increasing Subsequence) is a classical DP problem. It has the complexity of O(n²) if we follow the most classical DP algorithm. We can also improve the complexity to O(n log n). Detail can be found in my previous post.

In this article, I’d like to summarize some variations of LIS problems.

368. Largest Divisible Subset

From the official solution explanation[3]:

“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:

• Corollary I: 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 can understand the above claim from an example. For example:

if a set contains [1, 2, 4, 8], it is a valid set. If a new larger number (it is larger than all the elements in this set, this explains why we need sort the nuns to solve this problem), say 16, since 16%8 is 0, we can also get 16%4, 16%2, 16%1 is 0. Why? As 8 = 4k, 8=2l, 8 =1m. 16%8 is 2 it means 16 = 8f. Then for the relationship between 16 and 4, we can get 16 = 8f = (4k)f since 8 = 4k.

After understanding this one, it will be clear about why it can be implemented by following the LIS problem.

• In the LIS problem we are looking back and find whether X[-1]<current value. Where X is all feasible historical solutions end at X[-1]. Here X[-1] is following the python syntax which means the last element in X.
• In this problem, we are looking back and find whether current val% X[-1]==0.

The solution here is modified from [2]

class Solution:
    def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
        S = {1: set()}
        for x in sorted(nums):
            S[x] = max((S[d] for d in S if x % d == 0), key=len) | {x}
        return list(max(S.values(), key=len))

Thanks for reading. I am wondering whether we can improve the complexity of this algorithm to O(nlog n) by following what we did in the LIS problem. If the reader can find this solution, please share with me in the comments

Reference

[1]https://leetcode.com/problems/largest-divisible-subset/discuss/84006/Classic-DP-solution-similar-to-LIS-O(n2)

[2]https://leetcode.com/problems/largest-divisible-subset/discuss/84002/4-lines-in-Python

[3]https://leetcode.com/problems/largest-divisible-subset/solution/