Q44 Largest Divisible Subset - LeetCode 368

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;
    }
}