368. Largest Divisible Subset!

class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        // sort in ascending order
        Arrays.sort(nums);
        
        // stores the size if the largest set until index i of nums[]
        int[] memo = new int[nums.length];
        int[] prev = new int[nums.length];
        int index=0;
        for (int i=0; i<nums.length; i++){
            prev[i]=-1;
            memo[i]=1;
            for(int j=0; j<i; j++){
                if(nums[i]%nums[j]==0 && memo[j]+1>memo[i]){
                   memo[i]=memo[j]+1;
                   prev[i]=j; 
                }
            }
            index = memo[i]>memo[index]? i: index;
        }
        
        //generate the list and return;
        List<Integer> result = new ArrayList<>(memo[index]);
        result.add(nums[index]);
        int preIndex = prev[index];
        while(preIndex>=0){
            result.add(nums[preIndex]);
            preIndex=prev[preIndex];
        }
        return result;  
    }
}