Variations of LIS

  • 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.”
  • 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.
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))

--

--

--

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

The battle for 'enterprise cloud' is spilling into data centers and edge devices

Engineers: Stop using these terms…

100Days of Code #day 13

Big Data Processing using Apache Spark and Amazon Web Services

How Much Does It Cost To Build A Mobile App?

Docker Running In Rootless Mode

Session with Rails and learning React V6

Providing a better experience for .NET developers with Caller Argument Expressions

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi

More from Medium

Overcome Imbalance in your datasets — PART II

Memcached key distribution

Linear Regression Model Workflow

Analysing Weather Dataset Using Hadoop