class Solution { //https://www.youtube.com/watch?v=IFfYfonAFGc&list=PLgUwDviBIf0qUlt5H_kiKYaNSqJ81PMMY&index=43&ab_channel=takeUforward //https://leetcode.com/problems/largest-divisible-subset/solutions/84006/classic-dp-solution-similar-to-lis-o-n-2/ //Q-45 public List<Integer> largestDivisibleSubset(int[] nums) { //Sorting , writing LIS , modifying LIS to give me largest divisble subset //writing LIS such that we can print it using another Hash array. int n = nums.length; int[] dp = new int[n]; //every index will store maximum LIS till that element int[] hash = new int[n]; Arrays.sort(nums); int max = 0 , lastidx = -1; for(int i = 0 ;i < n ; i++){ dp[i] = 1 ; //basecase hash[i] = -1; for(int j = i-1 ; j >=0 ; j--){ if(nums[i] % nums[j] == 0 && 1+dp[j] > dp[i]){ dp[i] = 1+dp[j]; hash[i] = j; } } if(dp[i] > max){ max = dp[i]; lastidx = i; } } //printing using List<Integer> print = new ArrayList<>(); while(lastidx != -1){ print.add(nums[lastidx]); lastidx = hash[lastidx]; } System.out.println(max); return print; } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter