368. Largest Divisible Subset

Link

Solution

1. Sort the nums to facilitates the calculate

2. Find the maxLen of each stop Index i, dp[i] : the maxLen fo dividable set for nums[0] to nums[i]

   //Set all initial value, 
   //the minmun of the length should be 1 for any i
   Arrays.fill(dp, 1); 
   
   for(int i = 1; i < dp.length; i++){
       //trace back to see if there is any combination before nums[i] 
       //can make the sequence longer
       for(int j = i-1; j >= 0; j--){
           dp[i] = Math.max(dp[i], dp[j]+1);
       }
   } 

3. Find the maxIdx which point to the maxNum in the Set

4. Trace back to see which elements the maxLen generated from

int curLen = dp[maxIdx];
for(int i = maxIdx; i >= 0; i--){
    if(dp[maxIdx] % dp[i] == 0 && curLen == dp[i]){
        ret.add(nums[i]);
        curLen--;
    }
}

  public List<Integer> largestDivisibleSubset(int[] nums) {
        List<Integer> ret = new LinkedList<>();
        if(nums.length == 0) return ret;
        Arrays.sort(nums);
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        
        for(int i = 1; i < dp.length; i++){
            //look back, see if there is any conbination to make the sequence longer
            for(int j = 0; j < j; j++){
                if(nums[i] % nums[j] == 0){
                    dp[i] = Math.max(dp[i], dp[j]+1);
                }
            }
        }
        
        int maxIdx = 0;
        for(int i = 1; i < dp.length; i++)
        {
            if(dp[i] >= dp[maxIdx]){
                maxIdx = i;
            }
        }
        //To trace back where the sequence come from and add to list 
        int curLen = dp[maxIdx];
        for(int i = maxIdx; i >= 0; i--){
            if(nums[maxIdx]%nums[i] == 0 && dp[i] == curLen){
                ret.add(nums[i]);
                curLen--;
            }
        }
        return ret;
        
    }