Largest Divisible Subsets

跟LIC的DP做法很像，就是除了存一个dp的array以外，另外再维护一个indices的array，可以把顺序存下来。

public class Solution {
    public List<Integer> largestDivisibleSubset(int[] nums) {
        List<Integer> result = new LinkedList<Integer>();
        if (nums == null || nums.length == 0) {
            return result;
        } 

        Arrays.sort(nums);

        int m = nums.length;
        int[] dp = new int[m];
        int[] indices = new int[m];
        Arrays.fill(indices, -1);

        int last = -1;
        int max = 0;
        for (int i = 0; i < m; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] % nums[j] == 0) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        indices[i] = j;
                    }
                }
            }
            max = Math.max(max, dp[i]);
            if (dp[i] == max) {
                last = i;
            }
        }

        while (last != -1) {
            result.add(0, nums[last]);
            last = indices[last];
        }
        return result;

    }
}