Java | Reuse Longest Increasing Subsequence
Idea: Reuse LC 300. Longest Increasing Subsequence\n Sort nums\n Find size of longest divisible subset through the same approach as in LIS\n Construct LDS by it
**Idea:** Reuse [LC 300. Longest Increasing Subsequence](https://leetcode.com/problems/longest-increasing-subsequence/discuss/333005/Java-or-2-methods-or-DP-and-Patience-Sort)\n* Sort nums\n* Find size of longest divisible subset through the same approach as in LIS\n* Construct LDS by iterating through dp from right to left\n> **T/S:** O(n\xB2)/O(n) \n```\npublic List<Integer> largestDivisibleSubset(int[] nums) {\n\tvar dp = new int[nums.length];\n\treturn constructLDS(nums, dp, getLDSSize(nums, dp));\n}\n\nprivate int getLDSSize(int[] nums, int[] dp) {\n\tArrays.sort(nums);\n\tArrays.fill(dp, 1);\n\tvar ldsSize = 1;\n\n\tfor (var i = 1; i < nums.length; i++)\n\t\tfor (var j = 0; j < i; j++)\n\t\t\tif (nums[i] % nums[j] == 0) {\n\t\t\t\tdp[i] = Math.max(dp[i], dp[j] + 1);\n\t\t\t\tldsSize = Math.max(ldsSize, dp[i]);\n\t\t\t}\n\t\t\t\n\treturn ldsSize;\n}\n\nprivate List<Integer> constructLDS(int[] nums, int[] dp, int ldsSize) {\n\tvar prev = -1;\n\tvar lds = new LinkedList<Integer>();\n\n\tfor (var i = dp.length - 1; i >= 0; i--)\n\t\tif (dp[i] == ldsSize && (prev == -1 || prev % nums[i] == 0)) {\n\t\t\tlds.addFirst(nums[i]);\n\t\t\tldsSize--;\n\t\t\tprev = nums[i];\n\t\t}\n\n\treturn lds;\n}\n```\n***Please upvote if this helps***
['Java']