368. Largest Divisible Subset

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Dynamic Programming
 *
 * 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.
 *
 * Thus, we will sort the array and try to enlarge candidate solutions by
 * appending a larger element at the end of each potential set.
 *
 * DP[i] = Length of the largest divisible subset with A[i] as the largest value
 *
 * DP[i] = max(1 + DP[j]) where 0 <= j < i, if A[i] % A[j] == 0, else DP[i] = 1
 *
 * Time Complexity: O(N^2 + N log N). O(N log N) is for sorting.
 *
 * Space Complexity: O(N)
 *
 * N = Length of the input nums array.
 */
class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        List<Integer> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }

        if (nums.length == 1) {
            result.add(nums[0]);
            return result;
        }

        Arrays.sort(nums);
        int len = nums.length;
        int[] count = new int[len]; // Counts array
        int[] pred = new int[len]; // Predecessors array. This will be used to get the elements in the largest
                                   // subset.

        int maxCount = 0;
        int maxIdx = -1;

        for (int i = 0; i < len; i++) {
            count[i] = 1;
            pred[i] = -1;

            for (int j = 0; j < i; j++) {
                // count[j] can form a larger subset by adding nums[i] to existing subset with
                // nums[j] as the largest value.
                if (nums[i] % nums[j] == 0 && 1 + count[j] > count[i]) {
                    count[i] = 1 + count[j];
                    pred[i] = j;
                }
            }

            if (count[i] > maxCount) {
                maxCount = count[i];
                maxIdx = i;
            }
        }

        while (maxIdx != -1) {
            result.add(nums[maxIdx]);
            maxIdx = pred[maxIdx];
        }

        // Replace above while loop with this if the result is required in increasing
        // order. Also initialize the list as LinkedList.
        // while (maxIdx != -1) {
        // result.addFirst(nums[maxIdx]);
        // maxIdx = pred[maxIdx];
        // }

        return result;
    }
}