@@ -0,0 +1,2567 @@
+import java.util.ArrayList;%0Aimport java.util.Arrays;%0Aimport java.util.List;%0A%0A/**%0A * Given a set of distinct positive integers, find the largest subset such that every pair (Si, Sj) of elements in this%0A * subset satisfies: Si %25 Sj = 0 or Sj %25 Si = 0.%0A * %3Cp%3E%0A * If there are multiple solutions, return any subset is fine.%0A * %3Cp%3E%0A * Example 1:%0A * %3Cp%3E%0A * nums: %5B1,2,3%5D%0A * %3Cp%3E%0A * Result: %5B1,2%5D (of course, %5B1,3%5D will also be ok)%0A * Example 2:%0A * %3Cp%3E%0A * nums: %5B1,2,4,8%5D%0A * %3Cp%3E%0A * Result: %5B1,2,4,8%5D%0A * %3Cp%3E%0A * Tags: Dynamic Programming, Math%0A */%0Apublic class LargestDivisibleSubset %7B%0A%0A    /**%0A     * 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%0A     * divisible by the largest number of the set.%0A     * %3Cp%3E%0A     * Recurrent relation:%0A     * T%5Bn%5D = the length of the largest divisible subset whose largest number is a%5Bn%5D%0A     * T%5Bn+1%5D = max%7B 1 + T%5Bi%5D %7D if a%5Bn+1%5D mod a%5Bi%5D == 0 for 0%3C=i%3C=n, else 1%0A     * %3Cp%3E%0A     * Sort the array first.%0A     * Create an array named parent to record parent index of current element.%0A     * Create an array named count to record the largest subset of current element.%0A     * Then Start from one end of the array and try to find larger element that divides current element.%0A     * If it divides and subset size is smaller than that element + 1, then update size and parent.%0A     * If count is bigger than max, update max and max index.%0A     * Finally, recover the list of integers with parent array.%0A     */%0A    public List%3CInteger%3E largestDivisibleSubset(int%5B%5D nums) %7B%0A        if (nums == null) throw new NullPointerException(%22Input array nums is null%22);%0A        if (nums.length %3C= 1) throw new IllegalArgumentException(%22Input array must have at least 2 elements%22);%0A%0A        Arrays.sort(nums);%0A        int%5B%5D parent = new int%5Bnums.length%5D;%0A        int%5B%5D count = new int%5Bnums.length%5D;%0A        int max = 0;%0A        int maxIndex = -1;%0A        for (int i = nums.length - 1; i %3E= 0; i--) %7B%0A            for (int j = i; j %3C nums.length; j++) %7B%0A                if (nums%5Bj%5D %25 nums%5Bi%5D == 0 && count%5Bi%5D %3C 1 + count%5Bj%5D) %7B%0A                    count%5Bi%5D = 1 + count%5Bj%5D;%0A                    parent%5Bi%5D = j;%0A                    if (count%5Bi%5D %3E max) %7B%0A                        max = count%5Bi%5D;%0A                        maxIndex = i;%0A                    %7D%0A                %7D%0A            %7D%0A        %7D%0A%0A        List%3CInteger%3E res = new ArrayList%3C%3E();%0A        for (int i = 0; i %3C max; i++) %7B%0A            res.add(nums%5BmaxIndex%5D);%0A            maxIndex = parent%5BmaxIndex%5D;%0A        %7D%0A        return res;%0A    %7D%0A%7D%0A

add Largest Divisible Subset