368. Largest Divisible Subset

LeetCode Explaination

Quote:
"The key concept here is:

Given a set of integers that satisfies the property that each pair of integers inside the set are mutually divisible, for a new integer S, S can be placed into the set as long as it can divide the smallest number of the set or is divisible by the largest number of the set.

For example, let's say we have a set P = { 4, 8, 16 }, P satisfies the divisible condition. Now consider a new number 2, it can divide the smallest number 4, so it can be placed into the set; similarly, 32 can be divided by 16, the biggest number in P, it can also placed into P.

Next, let's define:

For an increasingly sorted array of integers a[1 .. n]

T[n] = the length of the largest divisible subset whose largest number is a[n]

T[n+1] = max{ 1 + T[i] if a[n+1] mod a[i] == 0 else 1 }

Now, deducting T[n] becomes straight forward with a DP trick. For the final result we will need to maintain a backtrace array for the answer."
 42.60%

public class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        List<Integer> result = new ArrayList<>();
        if (nums == null || nums.length == 0) return result;
        int[] maxLength = new int[nums.length];
        int[] prev = new int[nums.length];
        Arrays.sort(nums);
        maxLength[0] = 1;
        prev[0] = -1;
        int max = 0, index = 0;
        for (int curr = 1; curr < nums.length; curr++) {
            maxLength[curr] = 1;
            prev[curr] = -1;
            for (int i = 0; i < curr; i++) {
                if (nums[curr] % nums[i] == 0) {
                    if (maxLength[i] + 1 > maxLength[curr]) {
                        maxLength[curr] = maxLength[i] + 1;
                        prev[curr] = i;
                    }
                }
            }
            if (maxLength[curr] > max) {
                max = maxLength[curr];
                index = curr;
            }
        }
        //System.out.println(maxLength[index]);
     
        int size = maxLength[index];
        for (int j = 0; j < size; j++) {
            result.add(nums[index]);
            index = prev[index];
        }
     
        return result;
     
    }
}